Автоматы и формальные языки
Теория автоматов и формальных языков изучает идеализированные машины возрастающей мощности и классы строк, или языков, которые каждая из них может распознавать, давая точное математическое описание того, что считается паттерном и что требуется для его обнаружения.
Definition
Формальный язык — это множество конечных строк над фиксированным алфавитом, а автомат — это абстрактное вычислительное устройство, чьи принимающие вычисления определяют такой язык; эта область классифицирует языки по простейшему типу автомата или грамматики, которые их генерируют или распознают.
Scope
Эта область охватывает конечные автоматы и регулярные языки, магазинные автоматы и контекстно-свободные языки, иерархию Хомского, связывающую грамматики с моделями машин, свойства замыкания и разрешимости классов языков, а также автоматы, обрабатывающие бесконечные слова и деревья, вместе с сопровождающими их алгебраическими и логическими характеристиками.
Sub-topics
Core questions
- Какие языки может распознавать машина с конечной памятью и что она не может распознавать?
- Как грамматики и модели машин соотносятся на разных уровнях иерархии Хомского?
- Какие вопросы о классе языков, такие как пустота или эквивалентность, алгоритмически разрешимы?
- Как автоматы распространяются на бесконечные слова и деревья, и почему это важно для верификации?
Key theories
- Эквивалентность детерминированных и недетерминированных конечных автоматов
- Каждый недетерминированный конечный автомат может быть преобразован с помощью конструкции подмножеств в детерминированный, принимающий тот же язык, поэтому недетерминизм не добавляет распознающей мощности на конечно-автоматном уровне, хотя он может быть экспоненциально более лаконичным.
- Теорема Клини
- Языки, распознаваемые конечными автоматами, — это в точности регулярные языки, описываемые регулярными выражениями, что связывает машинный, алгебраический и грамматический подходы к простейшему классу языков.
- Иерархия Хомского
- Регулярные, контекстно-свободные, контекстно-зависимые и рекурсивно перечислимые языки образуют строгую цепочку включений, причем каждый уровень соответствует типу грамматики и модели автомата с соответствующей структурой памяти.
Clinical relevance
Конечные автоматы и регулярные выражения обеспечивают лексический анализ в компиляторах, поиск текста и спецификацию протоколов, в то время как контекстно-свободные грамматики лежат в основе синтаксического анализа языков программирования; автоматы над бесконечными объектами составляют алгоритмическое ядро верификации моделей (model checking), где система проверяется на соответствие спецификации темпоральной логики.
History
Конечно-автоматные модели возникли из нейронных сетей Мак-Каллока и Питтса в 1940-х годах и получили языково-теоретическую форму от Клини около 1951 года. Рабин и Скотт ввели недетерминированные автоматы в 1959 году, в то время как грамматики Хомского конца 1950-х годов организовали классы языков в иерархию, которая до сих пор структурирует эту область.
Key figures
- Stephen Kleene
- Michael Rabin
- Dana Scott
- Noam Chomsky
Related topics
Seminal works
- rabinScott1959
- sipser2013
- hopcroft2006
Frequently asked questions
- Почему конечный автомат не может распознавать сбалансированные скобки?
- Распознавание произвольно глубокой вложенности требует подсчета количества еще не сопоставленных открывающих скобок, что может превысить любое фиксированное число состояний. Конечный автомат имеет только ограниченную память, поэтому эта способность подсчета находится на один уровень выше, у магазинных автоматов и контекстно-свободных языков.
- Какова практическая польза теории формальных языков?
- Она сообщает инженерам, какие паттерны может выразить данный инструмент. Регулярных выражений достаточно для токенов, но не для вложенной структуры, поэтому компиляторы разделяют работу между регулярным лексером и контекстно-свободным парсером, и поэтому инструменты верификации полагаются на автоматы над бесконечными словами.