Конечные автоматы и регулярные языки

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

Definition

Конечный автомат — это машина с конечным набором состояний, функцией переходов по входным символам, начальным состоянием и принимающими состояниями; он принимает строку, если чтение строки переводит его из начального состояния в принимающее состояние, а множество принятых строк является его языком.

Scope

Эта тема охватывает детерминированные и недетерминированные конечные автоматы, их эквивалентность посредством конструкции подмножеств, регулярные выражения и теорему Клини, теорему Майхилла-Нерода и минимизацию состояний, свойства замкнутости регулярных языков и лемму о накачке, используемую для доказательства того, что определенные языки не являются регулярными.

Core questions

• Какие языки могут быть распознаны с использованием только фиксированного, конечного объема памяти?
• Почему детерминированные и недетерминированные конечные автоматы одинаково мощны?
• Как можно доказать, что конкретный язык не является регулярным?
• Какой автомат является наименьшим, распознающим данный регулярный язык?

Key theories

Конструкция подмножеств

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

Теорема Клини

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

Теорема Майхилла-Нерода

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

Clinical relevance

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

History

Опираясь на модель нервных сетей Мак-Каллока и Питтса 1943 года, Клини охарактеризовал события, которые могут быть представлены конечными автоматами, примерно в 1951 году, а Рабин и Скотт формализовали недетерминированные автоматы и их проблемы разрешимости в 1959 году, работа, позднее отмеченная премией Тьюринга.

Key figures

• Stephen Kleene
• Michael Rabin
• Dana Scott
• Anil Nerode

Seminal works

• rabinScott1959
• sipser2013

Frequently asked questions

Как показать, что язык не является регулярным?

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

Если недетерминированные автоматы не мощнее, зачем их использовать?

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