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

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

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

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

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

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

Следствия

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

См. также

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

Литература

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