Действительно ли Теория автоматов мертва? [закрытый]
9 ответов
Автоматы действительно полезны. Я получил степень по программной инженерии и информатике почти 20 лет назад. Одним из первых курсов были "Модели автоматов", в котором рассматривались FSA, а также немного токарных автоматов, вычислимость, проблема остановки и т. д.
Все считали этот курс скучным, неактуальным, слишком трудным или бессмысленным. Круги и дуги не имели никакого смысла, и какой смысл в ленте, на которой только единицы? Что плохого в жестком диске? В конце курса лектор раздал анкету - как вы думаете, насколько полезен будет этот курс через месяц, через год, через десять лет. Тогда я ответил - не полезен для всех. Теперь я буду увеличивать полезность со временем, заканчивая "очень полезным"
Я много использовал автоматы в своей повседневной работе, и они являются подходящим инструментом для определенных классов проблем, с которыми мало кто может конкурировать. Я использовал их для сжатия многомиллионных списков слов + данные о категориях (ладно, довольно банально), а также реализовал расширение, в котором символы являются сложными объектами, а переходы состояний - предикатами. Это позволило скомпилировать сложный набор правил в детерминированный FST и оценить все правила одновременно и детерминированно без лишних вычислений.
Мой голос - за актуальность!
Это не умерло, скорее, «готово к изучению» - это простой формализм, который используется больше в качестве основы для других, а не является особенно активной темой исследования.
Работа Генри Томпсона над схемами XML использует и расширяет теорию автоматов.
Во многих проектах встроенного программного обеспечения интенсивно используются конечные автоматы, связанные с автоматами, а некоторые методы работы с ними основываются на теории автоматов или расширяют ее.
Пи-исчисление расширяет теорию автоматов концепцией бисимуляции и добавляет возможности для анализа параллельных процессов. Это самое близкое недавнее исследование к теории автоматов, которую я изучал в университете.
Автоматы и формальные языки являются основой регулярных выражений, синтаксических анализаторов, компиляторов, виртуальных машин и т.д., которые регулярно совершенствуются.
В области проверки теорем для проверки программ, целью которой является доказательство того, что программа или протокол достигают того, на что претендуют. Эта область является критически важной (программное обеспечение машин для голосования, банковские транзакции, системы безопасности в автомобилях и т.д.) и все еще находится в стадии разработки.
Так что нет, теория автоматов и формальные языки не умерли!
Я думаю, что теория автоматов задействована во многих областях без осознания этого людьми. Например, я вижу ее применение в криптографии и криптоанализе.
Я думаю, что по мере открытия новых областей вычислений, таких как квантовые вычисления и гипервычисления, появятся новые приложения, требования, требования и теоретические выкладки из теории автоматов и таких вещей, как эволюционные автоматы и вычисления, клеточные автоматы и тому подобное.
Я не думаю, что она мертва, просто немного остыла на данный момент.
Один из новых методов, с которым я столкнулся несколько лет назад, называется синтаксическим анализом грамматик выражений, он же PEG, он же Packrat Parsing. Брайан Форд проделал некоторую работу над этим, которую можно посмотреть по адресу http://pdos.csail.mit.edu/~baford/packrat/ .
По сути, это анализатор с нисходящим рекурсивным спуском, и одним из его преимуществ является то, что лексический анализ и семантический анализ могут выполняться за один шаг.
PEG по сравнению с CFG в том, что PEG больше подходят для синтаксического анализа контекстно-свободного языка, тогда как CFG больше подходят для создания контекстно-свободного языка.
многое из управления процессами в значительной степени основано на теории. Особенно с точки зрения доказательства устойчивости систем управления.
Взгляните на процессы рабочего процесса и посмотрите, как теория автоматов может быть использована там для формализации описанных концепций и шаблонов: Шаблоны рабочего процесса
Вместо того, чтобы считать теорию мертвой, подумайте о том, что она стала настолько практичной для приложений, что мы вышли за рамки теории. Отличной книгой, наводящей мосты между теорией и приложениями, является книга Миро Самека "Practical Statecharts in C/C++". Сейчас доступно второе издание, которое я не читал. Но в первом издании я не нашел ничего недостаточного; по сей день я считаю его одним из самых ценных текстов, которые я когда-либо читал.