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

В теории формальных языков теорема Майхилла — Нероуда определяет необходимое и достаточное условия регулярности языка.

Теорема названа в честь Шаблон:Не переведено 3 и Шаблон:Не переведено 3, доказавших её в Чикагском университете в 1958 году.

Формулировка теоремы

Пусть существует язык $L$ в алфавите $V$ и задано отношение ${\equiv }_L$ на словах из множества всех слов в данном алфавите такое, что $x{\equiv }_{L}y$ тогда и только тогда, когда для всех $z$, принадлежащих множеству всех слов в данном алфавите, оба слова $xz$ и $yz$ одновременно принадлежат или одновременно не принадлежат языку $L$. Нетрудно доказать, что ${\equiv }_L$ — отношение эквивалентности на множестве слов в алфавите $V$.

По теореме Майхилла — Нероуда число состояний в минимальном детерминированном конечном автомате (ДКА), допускающем язык $L$, равно числу классов эквивалентности по отношению ${\equiv }_L$, то есть, мощности фактормножества языка $L$ относительно ${\equiv }_L$. Данное число также называется индексом бинарного отношения и обозначается как $ind{\equiv }_L$.

Следствия

Из теоремы Майхилла — Нероуда следует, что язык $L$ регулярен тогда и только тогда, когда число классов эквивалентности по ${\equiv }_L$ конечно. Можно сразу же заключить, что если отношение ${\equiv }_L$ разбивает язык $L$ на бесконечное число классов эквивалентности, то язык $L$ не регулярен. Это заключение очень часто используется для доказательства нерегулярности языков.

См. также

• Лемма о разрастании

Литература

• Tom Henzinger, Lecture 7: Myhill-Nerode Theorem (2003)
• Теорема Майхилла-Нероуда (конспекты занятий по курсу «Теория и реализация языков программирования», ФУПМ МФТИ).