Всегда есть способ применения в темах, связанных с теоретической информатикой. Но учебники и курсы бакалавриата обычно не объясняют причину, по которой теория автоматов является важной темой и имеет ли она применение на практике. Поэтому у студентов бакалавриата могут возникнуть проблемы с пониманием важности теории автоматов, и они могут подумать, что она больше не имеет практического применения.
Теория автоматов все еще полезна на практике?
Это должно быть частью учебной программы бакалавриата CS?
soft-question
fl.formal-languages
automata-theory
teaching
Темный тамплиер
источник
источник
Ответы:
Вы когда-нибудь использовали такой инструмент, как grep / awk / sed? Регулярные выражения составляют основу этих инструментов.
Вы будете удивлены, сколько кода вы можете избежать, используя принципиальное использование регулярных выражений - в «практических проектах», таких как почтовый сервер.
Если вы - специалист по CS, вы обязательно напишите компилятор / интерпретатор для (хотя бы небольшого) языка. Если вы когда-либо пробовали эту задачу раньше и застряли, вы по достоинству оцените, насколько вам может помочь небольшая теория (иначе говоря, контекстно-свободные грамматики). Эта теория превратила некогда невыполнимую задачу в нечто, что может быть выполнено за выходные. (И он выиграл изобретатель награду Тьюринга - Google BNF).
Если вы являетесь специалистом по CS, в какой-то момент вам нужно откинуться на спинку кресла и подумать о философских основах вычислений, а не только о том, насколько крута следующая версия API Android. В связи с этим, работа университета заключается не в том, чтобы подготовить вас к следующим 5 годам вашей жизни, но подготовить вас к следующим 50 годам. Единственное, что они могут сделать в этом отношении, это помочь вам думать - думать теории автоматов как один из тех курсов.
источник
Одним из наиболее практичных проявлений CS является компиляция конструкции. В 1965 году Кнут начал изучать парсеры LR. Быстро (менее чем за десятилетие) у нас появились парсеры LALR, которые являются подмножеством детерминированных автоматов с понижением частоты, которые позволяют нам реализовывать парсеры сдвига / уменьшения.
В основе осуществимости и эффективности анализа LALR лежит доказательство (Кнутом) того, что «префиксы» языка оказываются регулярными (ваш конечный автомат). Это происхождение автоматических генераторов парсеров, таких как yacc / bison и т. Д.
Можно с уверенностью сказать, что языки программирования, какими мы их знаем, во многом обязаны своим разработкам этим разработкам.
Вот еще один пример: сердце протокола TCP / IP - это конечный автомат. Насколько более практичным это может быть?
Каждый серьезный студент CS, особенно практический, должен обратить внимание на теорию автоматов. Это основа для большей части компьютерных наук.
источник
Вы слышите этот шум ? Это звук тысячи блестящих теорем, приложений и инструментов, смеющихся в автомате-теоретическом раю.
Языки и автоматы - это элегантные и надежные концепции, которые вы найдете в любой области информатики. Языки - это не сухая формалистическая затея с предысторией вычислений. Перспектива теории языка разбирает кажущиеся сложными вопросы о сложных непрозрачных объектах в простые утверждения о словах и деревьях. Формальные языки играют роль в информатике, сродни фундаментальной и изменяющей игру точке зрения, привнесенной алгеброй и топологией в классическую математику. Вот некоторые практические, довольно сложные, практические проблемы, которые решаются с помощью теории языка.
Упомянутая выше редукция рассматривает языки как абстрактные математические объекты. Чтобы применить эти идеи на практике, нам нужна структура данных для представления языков и алгоритмов для манипулирования этими структурами данных.
Введите автомат. Автоматы позволяют свести вопросы об абстрактных математических объектах, таких как языки, к конкретным алгоритмическим вопросам о помеченных графах. Теория языков и автоматов, помимо безумного количества практических приложений, обеспечивает очень важную интеллектуальную услугу. Мы можем думать о проблемах, начиная от форматирования почтовых индексов и заканчивая процедурами принятия решений для монадической логики второго порядка в единообразном и незагроможденном концептуальном пространстве. Как это удивительно!
Я ничего не сказал о логике и процедурах принятия решений. (Да, они имеют практическое применение.) См. Ответ Каве для авторитетного обзора.
источник
Как объяснялось в других ответах, теория автоматов важна концептуально как простая вычислительная модель, которую мы хорошо понимаем, и регулярные выражения и автоматы имеют много реальных приложений.
Вот небольшой пример для современных исследований, который восходит к теории автоматов, чтобы понять современную концепцию. В этой статье исследователи доказывают, что все обычные языки имеют тестеры свойств: «Обычные языки тестируются с постоянным количеством запросов»
источник
Это не просто ванильные автоматы. Вы изучаете основы (принятие состояний, эпсилон-переходы, ...) (вычислительной) модели, которая помогает рассуждать о том, что может, и, что более важно, о том, что не может быть выражено некоторыми языками запросов. Несколько интересных результатов включают в себя:
(и конечно я пропускаю много других классов)
По сути, это очень общая модель. Ваши классы, вероятно, подчеркнут связь между автоматами, языками и логикой.
Если бы я хотел связать это с конкретными «мирскими» инструментами, я бы провел свободное время в библиотеке, читая пару частей (AB?) Из Оснований баз данных Abiteboul & al, и пытаясь соединить это с материалами класса , Конечно, это всего лишь один из (многих) способов поиска приложений класса автоматов, и я думаю, что не самый очевидный - но именно поэтому это интересное упражнение.
источник
Как уже указывалось в различных ответах, теория автоматов в курсах UG дает одну базовую концептуальную основу для введения более сложных (и практических) тем, а также для выявления пропущенных связей; например: двоичные диаграммы принятия решений (они сводят к минимуму DFA; после обучения DFA я часто преподаю решение головоломок на основе BDD); создание сценариев, в том числе в BioPerl и BioPython (и отличная настройка, позволяющая увеличить количество непреднамеренных совпадений, которые могут быть скрыты в регулярных выражениях сценариев в реальном мире), формальная отладка (свойства состояния, такие как отрицание FA, пересечение), и даже программирование тревоги видеомагнитофона или домашнего нарушителя (каждый день стрессовая ситуация с плохо определенным автоматом преподается на неполных примерах; возможно, формализована с использованием синтеза пользовательских интерфейсов, основанного на сценариях воспроизведения и воспроизведения Харела). Я также использую настройки, чтобы научить Python
источник
Я выброшу другой ответ с совершенно иной практической точки зрения: конечные автоматы (или, по крайней мере, некоторые их простые обобщения / расширения) часто используются на стороне ИИ в программировании игр. Они оказываются отличной моделью для инкапсуляции поведения персонажа; например, у врага могут быть состояния, представляющие «патруль», «поиск», «подход», «атака», «защита», «отступление», «смерть» и т. д. с четко определенными переходами между ними. Это не касается каких-либо формальных аспектов автоматов, таких как обычные языки и тому подобное, но концепция автомата является очень базовой.
источник
- Джеймс Милль (псевдоним «PQ»), «Теория и практика», Лондон и Вестминстерское обозрение , апрель 1836 г.
источник
Были проведены значительные исследования, связанные с теорией автоматов при проверке моделей, используемой в промышленности. Ознакомьтесь с недавними лекциями Моше Варди в Fields Institute , в частности с 3-й лекцией «Логика, автоматы, игры и алгоритмы», чтобы понять, почему теория автоматов все еще важна и полезна.
Слайды и аудиофайлы лекций доступны здесь: 1 , 2 , 3 .
источник
Мы должны учитывать семантику слов «практический» и «применение». Для некоторых студентов практическим является все, что поможет им сдать экзамены; для других - все, что может возникнуть на работе. В обоих случаях теория автоматов действительно очень практична.
Как отмечают другие, вы будете использовать грамматики, например, при изучении компиляторов. Но даже более того: понимание всей концепции наличия разных состояний и правил для переходов между ними может сделать вас лучшим программистом, когда вы поймете, например, что ваш код избыточен здесь и там, и что когда вы его улучшаете, вы применяют в своем коде те же концептуальные идеи, которые лежат в основе минимизации DFA.
Аналогично для «приложения». Что вы понимаете под этим словом? Даже если вы «практичный инженер», вы увидите и будете использовать идеи, схожие с идеями теории автоматов в реальных проектах: программный код, блок-схемы и даже простую, но блестящую концепцию стека. Для таких теоретиков, как я, я рассматриваю применение теории автоматов в других областях, таких как логика, алгебра и теория конечных моделей. Конечно, мне, вероятно, никогда не понадобится использовать насосную лемму при совершении покупок в супермаркете, но подобные теоремы помогли мне понять структуру определенных классов языков, не говоря уже о структурах логики и алгебраики, с которыми они соответствуют. И это то, что я ценю больше, чем любая мера практичности.
источник
Объединенные с логикой, автоматы могут предложить способы проверки государственных деятелей, таких как
для автомата и формулы . Если является моделью системы и формализацией желаемых свойств, вы получаете проверку системы, что очень практично для растущего числа возможных приложений.φ A φA φ A φ
Учет автоматной стороны вещей приводит к хорошим алгоритмам. Например, если - формула LTL, а - автомат Бучи (т. Е. Бесконечно работающий конечный автомат), вы можете перевести в эквивалентный автомат и проверить, не является лиA φ A φ L ( A ) ⊆ L ( A φ )φ A φ Aφ L(A)⊆L(Aφ)
источник
Конечные автоматы, часто описываемые как конечные автоматы в разных контекстах или с их вероятностными вариантами, могут быть применены скрытые марковские модели для распознавания и количественного определения структуры шаблона. Например, что является наименьшим стохастическим конечным автоматом, который будет генерировать строки в соответствии с более или менее заданным распределением вероятностей или сопоставлять статистические свойства выборки строк (или временных рядов) из некоторого распределения.
См., Например, CSSR , алгоритм слепого восстановления скрытых состояний; это более эффективно и гибко, чем скрытые марковские модели.
источник
Еще одним более практическим применением теории автоматов является развитие искусственного интеллекта. Искусственный интеллект был разработан на основе концепции конечного автомата. Нейронная сеть роботов построена на основе теории автоматов. Ведь роботы тоже автоматы.
источник
Некоторые дали отличные ответы, когда речь заходит о том, как это связано с промышленностью. Что должно быть важно, так это его научная ценность, и теория автоматов часто является дверью, позволяющей сначала понять более высокий уровень теории вычислений в исследованиях студентов. Теория автоматов имеет большой набор теорем, которые всплывают повсюду в теоретической информатике, особенно когда кто-то хочет поговорить о приложении, таком как компиляторы. Его научная ценность (она не устарела, как это может быть? Это основная теория в этой области) практична для любого ученого, который интересуется вычислениями. Это практично, так как это знание полезно тем, кто понимает или хочет понять природу вычислений. Если вы не можете найти в нем применение, я ставлю под сомнение исследования или даже намерение изучать CS, поскольку это не программирование (это
источник