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

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

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

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

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

Пусть существует язык $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\!$ не регулярен. Это заключение очень часто используется для доказательства нерегулярности языков.

См. также

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

Примечания

1. ↑ A. Nerode, «Linear automaton transformations», Proceedings of the AMS, 9 (1958) pp 541—544.

Литература

• Tom Henzinger, Lecture 7: Myhill-Nerode Theorem (2003)