Теория автоматов мертва?

Мне понравился курс, который я получил в Теории автоматов и формальных языках, поэтому, естественно, я начал оглядываться на промежутки, чтобы узнать, что произошло с того времени, когда были написаны книги, на которых основывался курс.

Я обнаружил, что список вещей, которые я не знал, казался очень коротким. Например, из списка автомата в записи в Википедии для предмета половина была охвачена курсом, а другая половина была в основном связана с одним языком, не охваченным курсом.

Кроме того, при изучении приложений теории я получил в основном те же результаты: синтаксис языка программирования, компиляторы, текстовый поиск и... что об этом.

Так действительно ли это мертво? Или он продолжает развиваться? Существуют ли новые приложения для теории?

Ответ 1

Автоматы действительно полезны. Я закончил свою степень в области разработки программного обеспечения и компьютерных наук почти 20 лет назад. Одним из первых курсов были модели машин, которые охватывали FSA, и немного отважились на токарные машины, вычислимость, проблемы с остановкой и т.д.

Все считали, что этот курс был либо скучным, неактуальным, либо слишком трудным или бессмысленным. Круги и дуги ни для кого не имели никакого смысла, и какова точка ленты с единственными на ней? Что случилось с жестким диском? В конце курса лектор выдал анкету - насколько полезен, по вашему мнению, этот курс будет через месяц, через год, через десять лет. Тогда я ответил, что не полезен для всех. Теперь это будет увеличивать полезность со временем, заканчиваясь "очень полезным"

Я использовал автоматы в моей дневной работе, и они являются подходящим инструментом для определенных классов проблем, и с ним еще мало чего конкурировать. Я использовал их для сжатия многомиллионных списков слов + данных категории (хорошо, довольно банально), а также реализовал расширение, где символы являются сложными объектами, а переходы состояний являются предикатами. Это позволило скомпилировать сложный набор правил для детерминированного FST и всех правил, оцениваемых одновременно и детерминистически без избыточных вычислений.

Мое голосование по-прежнему актуально!

Ответ 2

Автоматы и формальные языки являются основой регулярных выражений, парсеров, компиляторов, виртуальных машин и т.д., которые регулярно улучшаются.

Также требуются в области проверки теоремы для проверки программы, которая направлена на то, чтобы доказать, что программа или протокол достигает того, что она делает. Этот домен является критическим (программное обеспечение для голосования, банковские операции, системы безопасности в транспортном средстве и т.д.) И все еще находится в разработке.

Нет, теория автоматов и формальные языки не мертвы!

Ответ 3

Это не мертво, больше "выведено на стол" - это простой формализм, который больше используется как основа для других, а не является особенно активной темой исследования.

Генри Томпсон работает над XML-схемами, использует и расширяет теорию автоматов.

Многие проекты встроенного программного обеспечения сильно используют конечные машины, связанные с автоматами, а некоторые из методов работы с ними используют или расширяют теорию автоматов.

Pi-calculus расширяет теорию автоматов с концепцией бисимуляции и добавляет возможности для анализа параллельных процессов. Это ближайший бит недавних исследований теории автоматов, которые я изучил в университете.

Ответ 4

Я думаю, что в качестве новых областей вычислений, таких как квантовые вычисления и hypercomputation, откроются новые требования к приложениям, требования и теоретический бред из теории автоматов и таких вещей, как эволюционные автоматы и вычисления, клеточные автоматы и еще что-то.

Я не думаю, что он мертв, немного холодно на данный момент.

Ответ 5

Я думаю, что Automata Theory участвует во многих областях, где люди не понимают. Например, я вижу это приложение в криптографии и криптоанализе.

Ответ 6

много элементов управления процессом в значительной степени основано на теории. Особенно в плане доказательства надежности систем управления.

Ответ 7

Взгляните на процессы документооборота и посмотрите, как можно использовать теорию автоматов в формализации описанных понятий и шаблонов: Шаблоны рабочих процессов

Ответ 8

Один из новых техник, с которыми я столкнулся несколько лет назад, называется парсинг-выражениями грамматики, а также PEGs, например, Packrat Parsing. Брайан Форд проделал над ним некоторые работы, которые можно просмотреть на http://pdos.csail.mit.edu/~baford/packrat/.

Это в основном рекурсивный парсер спуска вниз, и одним из преимуществ этого является то, что лексический анализ и семантический анализ могут быть выполнены за один шаг.

Сравнение PEG с CFG в том, что PEG больше подходят для разбора контекстно-свободного языка, тогда как CFG больше подходят для создания контекстно-свободного языка.

Ответ 9

Вместо того, чтобы рассматривать теорию как мертвую, вместо этого подумайте, что она стала настолько практичной для приложений, которые мы вышли за рамки теории. Отличная книга, чтобы рассмотреть, что мосты между теорией и применением - это Миро Самек " Практические диаграммы состояния в C/С++". Сейчас доступно второе издание, которое я не читал. Но я ничего не нашел в первом издании; и по сей день я считаю это одним из самых ценных текстов, которые я когда-либо читал.