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

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

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

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

Формулировка теоремы[править | править вики-текст]

Пусть существует язык в алфавите и задано отношение на словах из множества всех слов в данном алфавите такое, что тогда и только тогда, когда для всех , принадлежащих множеству всех слов в данном алфавите, оба слова и одновременно принадлежат или одновременно не принадлежат языку . Нетрудно доказать, что  — отношение эквивалентности на множестве слов в алфавите .

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

Доказательство[править | править вики-текст]

Следствия[править | править вики-текст]

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

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

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

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