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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Теорема названа в честь Джона Майхилла (англ.)русск. и Энила Нероуда (англ.)русск., доказавших её в Чикагском университете в 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.

Литература[править | править вики-текст]