В теории формальных языков теорема Майхилла — Нероуда определяет необходимое и достаточное условия регулярности языка.
Теорема названа в честь Джона Майхилла[англ.] и Энила Нероуда[англ.], доказавших её в Чикагском университете в 1958 году.[1]
Пусть существует язык L {\displaystyle L} в алфавите V {\displaystyle V} и задано отношение ≡ L {\displaystyle \equiv _{L}} на словах из множества всех слов в данном алфавите такое, что x ≡ L y {\displaystyle x\equiv _{L}y} тогда и только тогда, когда для всех z {\displaystyle z} , принадлежащих множеству всех слов в данном алфавите, оба слова x z {\displaystyle xz} и y z {\displaystyle yz} одновременно принадлежат или одновременно не принадлежат языку L {\displaystyle L} . Нетрудно доказать, что ≡ L {\displaystyle \equiv _{L}} — отношение эквивалентности на множестве слов в алфавите V {\displaystyle V} .
По теореме Майхилла — Нероуда число состояний в минимальном детерминированном конечном автомате (ДКА), допускающем язык L {\displaystyle L} , равно числу классов эквивалентности по отношению ≡ L {\displaystyle \equiv _{L}} , то есть, мощности фактормножества языка L {\displaystyle L} относительно ≡ L {\displaystyle \equiv _{L}} . Данное число также называется индексом бинарного отношения и обозначается как i n d ≡ L {\displaystyle ind\equiv _{L}} .
Из теоремы Майхилла — Нероуда следует, что язык L {\displaystyle L} регулярен тогда и только тогда, когда число классов эквивалентности по ≡ L {\displaystyle \equiv _{L}} конечно. Можно сразу же заключить, что если отношение ≡ L {\displaystyle \equiv _{L}} разбивает язык L {\displaystyle L} на бесконечное число классов эквивалентности, то язык L {\displaystyle L} не регулярен. Это заключение очень часто используется для доказательства нерегулярности языков.