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

Теорема названа в честь (англ.) ( и (англ.) ( , доказавших её в Чикагском университете в 1958 году .

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

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

См. также

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

Примечания

Литература

• Tom Henzinger, (2003)
• (конспекты занятий по курсу «Теория и реализация языков программирования», ФУПМ МФТИ).

В статье не хватает ссылок на источники (см. рекомендации по поиску ). Информация должна быть проверяема , иначе она может быть удалена. Вы можете статью, добавив ссылки на авторитетные источники в виде сносок . ( 19 июня 2018 )