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

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

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

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

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

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

Доказательство

Следствия

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

См. также

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

Примечания

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

Литература

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