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

Материал из Seo Wiki - Поисковая Оптимизация и Программирование

Перейти к: навигация, поиск

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

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

Содержание

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

Пусть существует язык <math>L\!</math> в алфавите <math>V\!</math> и задано отношение <math>\equiv_L</math> на словах из множества слов в данном алфавите такое, что <math>x\equiv_L y</math> тогда и только тогда, когда для всех <math>z\!</math>, принадлежащих множеству слов в данном алфавите, оба слова <math>xz\!</math> и <math>yz\!</math> одновременно принадлежат или одновременно не принадлежат языку <math>L\!</math>. Нетрудно доказать, что <math>\equiv_L</math> — отношение эквивалентности на множестве слов в алфавите <math>V\!</math>.

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

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

Следствия

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

См. также

Примечания

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

Литература


cs:Myhillova-Nerodova věta

de:Satz von Myhill-Nerode en:Myhill–Nerode theorem he:משפט נרוד hr:Myhill-Nerode teorem it:Teorema di Myhill-Nerode ja:マイヒル-ネローデの定理 pl:Twierdzenie Myhilla-Nerode'a zh:迈希尔-尼罗德定理

Личные инструменты

Served in 0.140 secs.