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

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

Теорема названа в честь Джона Майхилла и Энила Нероуда, доказавших её в Чикагском университете в 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)
• Теорема Майхилла-Нероуда (конспекты занятий по курсу «Теория и реализация языков программирования», ФУПМ МФТИ).