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

В теории формальных языков теорема Майхилла -Нерода обеспечивает необходимое и достаточное условие языка регулярности . Теорема названа в честь Джона Майхилла и Анила Нерода , которые доказали ее в Чикагском университете в 1957 году ( Nerode & Sauer 1957 , стр. ii).

Заявление

Учитывая язык $L$и пара строк $x$ и $y$, определите отличительное расширение как строку $z$ такой, чторовно одна из двух строк $xz$ и $yz$ принадлежит $L$.Определить отношение $\sim _{L}$ на струнах как $x\;\sim _{L}\ y$ если нет отличительного расширения для $x$ и $y$. Легко показать, что $\sim _{L}$ является отношением эквивалентности строк и, таким образом, делит множество всех строк на классы эквивалентности .

Теорема Майхилла – Нероде утверждает, что язык $L$ регулярно тогда и только тогда, когда $\sim _{L}$ имеет конечное число классов эквивалентности, причем это число равно числу состояний минимального детерминированного конечного автомата (МКА), допускающего $L$. Более того, каждый минимальный ДКА языка изоморфен каноническому ( Хопкрофт и Ульман, 1979 ).

Майхилл, Нерод (1957) - (1) $L$ регулярно тогда и только тогда, когда $\sim _{L}$ имеет конечное число классов эквивалентности.

(2) Это число равно числу состояний минимального детерминированного конечного автомата (МДКА), допускающего $L$.

(3) Любой минимальный акцептор ДКА языка изоморфен следующему:

Пусть каждый класс эквивалентности $[x]$ соответствуют состоянию, и пусть переходы между состояниями будут $a:[x]\to [xa]$ для каждого $a\in \Sigma$. Пусть начальное состояние будет $[\epsilon ]$, а принимающие состояния будут $[x]$ где $x\in L$.

В общем случае для любого языка построенный автомат является акцептором автомата состояний . Однако он не обязательно имеет конечное число состояний. Теорема Майхилла-Нерода показывает, что конечность необходима и достаточна для регулярности языка.

Некоторые авторы обращаются к $\sim _{L}$ отношение как соответствие Нерода , в честь Анила Нероде .

Доказательство

(1) Если $L$ является регулярным. создайте минимальный DFA, чтобы принять его. Ясно, что если $x,y$ оказаться в том же состоянии после прохождения DFA, а затем $x\sim _{L}y$, таким образом, количество классов эквивалентности $\sim _{L}$ не более числа состояний DFA, которое должно быть конечным.

И наоборот, если $\sim _{L}$ имеет конечное число классов эквивалентности, то автомат, построенный в теореме, является акцептором ДКА, следовательно, язык регулярен.

(2) По построению (1).

(3) Учитывая минимальный акцептор DFA $A$, построим изоморфизм каноническому.

Построим следующее отношение эквивалентности: $x\sim _{A}y$ тогда и только тогда, когда $x,y$ оказаться в том же состоянии при прохождении $A$.

С $A$ является акцептором, если $x\sim _{A}y$ затем $x\sim _{L}y$. Таким образом, каждый $\sim _{L}$ Класс эквивалентности – это объединение одного или нескольких классов эквивалентности. $\sim _{A}$. Далее, поскольку $A$ минимально, число состояний $A$ равно числу классов эквивалентности $\sim _{L}$ по части (2). Таким образом $\sim _{A}=\sim _{L}$.

Теперь это дает нам биекцию между состояниями $A$ и состояния канонического акцептора. Ясно, что эта биекция также сохраняет правила перехода и, следовательно, является изоморфизмом ДКА.

Использование и последствия

Теорему Майхилла – Нероде можно использовать, чтобы показать, что язык $L$ является регулярным , доказав, что количество классов эквивалентности $\sim _{L}$ конечно. Это можно сделать путем исчерпывающего анализа случая , в котором, начиная с пустой строки , различающие расширения используются для поиска дополнительных классов эквивалентности до тех пор, пока больше не будет найдено. Например, регулярным является язык, состоящий из двоичных представлений чисел, которые делятся на 3. Учитывая пустую строку, $00$ (или $11$), $01$, и $10$ являются различающими расширениями, в результате чего образуются три класса (соответствующие числам, которые дают остатки 0, 1 и 2 при делении на 3), но после этого шага различающего расширения больше нет. Минимальный автомат, принимающий наш язык, будет иметь три состояния, соответствующие этим трем классам эквивалентности.

Другое непосредственное следствие теоремы состоит в том, что если для языка $L$ отношение $\sim _{L}$ имеет бесконечное число классов эквивалентности, то оно не является регулярным. Именно это следствие часто используется для доказательства того, что язык не является регулярным.

Обобщения

Теорему Майхилла-Нерода можно обобщить на древесные автоматы .

См. также

• Лемма о накачке для регулярных языков — альтернативный метод доказательства того, что язык не является регулярным. Лемма о накачке не всегда может доказать, что язык не является регулярным.
• Синтаксический моноид

Ссылки

• Хопкрофт, Джон Э .; Уллман, Джеффри Д. (1979), «Глава 3.4», Введение в теорию автоматов, языки и вычисления , Ридинг, Массачусетс: Addison-Wesley Publishing, ISBN  0-201-02988-Х .
• Нерод, Анил (1958), «Линейные автоматные преобразования», Труды Американского математического общества , 9 (4): 541–544, doi : 10.1090/S0002-9939-1958-0135681-9 , JSTOR   2033204 .
• Нерод, Анил; Зауэр, Бертон П. (ноябрь 1957 г.), Фундаментальные концепции теории систем (Технический отчет WADC), Центр развития авиации Райта . Документ ASTIA № AD 155741.
• Риган, Кеннет (2007), Заметки по теореме Майхилла-Нерода (PDF) , получено 22 марта 2016 г.

Дальнейшее чтение

• Бахадыр Хусаинов; Анил Нероде (6 декабря 2012 г.). Теория автоматов и ее приложения . Springer Science & Business Media. ISBN  978-1-4612-0171-7 .