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

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

Теорема названа в честь Джона Майхилла и Энила Нероуда, доказавших её в Чикагском университете в 1958 году.

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

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

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

Следствия

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

См. также

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

Литература

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