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

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

В теории формальных языков теорема Майхилла–Нерода обеспечивает необходимое и достаточное условие регулярности языка . Теорема названа в честь Джона Майхилла и Анила Нерода , которые доказали ее в Чикагском университете в 1957 году (Nerode & Sauer 1957, p. ii).

Заявление

Для данного языка и пары строк и определите различающее расширение как строку, такую, что ровно одна из двух строк и принадлежит . Определим отношение на строках так, как будто нет различающего расширения для и . Легко показать, что является отношением эквивалентности на строках, и, таким образом, оно делит множество всех строк на классы эквивалентности . ${\displaystyle L}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle z}$ ${\displaystyle xz}$ ${\displaystyle yz}$ ${\displaystyle L}$ ${\displaystyle \sim _{L}}$ ${\displaystyle x\;\sim _{L}\ y}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle \sim _{L}}$

Теорема Майхилла–Нерода утверждает, что язык является регулярным тогда и только тогда, когда имеет конечное число классов эквивалентности, и, более того, это число равно числу состояний в минимальном детерминированном конечном автомате (DFA), принимающем . Более того, каждый минимальный DFA для языка изоморфен каноническому (Hopcroft & Ullman 1979). ${\displaystyle L}$ ${\displaystyle \sim _{L}}$ ${\displaystyle L}$

Майхилл, Нерод (1957)  —  (1) является регулярным тогда и только тогда, когда имеет конечное число классов эквивалентности. ${\displaystyle L}$ ${\displaystyle \sim _{L}}$

(2) Это число равно числу состояний в минимальном детерминированном конечном автомате (ДКА), принимающем . ${\displaystyle L}$

(3) Любой минимальный акцептор DFA для языка изоморфен следующему:

Пусть каждый класс эквивалентности соответствует состоянию, и пусть переходы состояний будут для каждого . Пусть начальное состояние будет , а принимающие состояния будут , где . ${\displaystyle [x]}$ ${\displaystyle a:[x]\to [xa]}$ ${\displaystyle a\in \Sigma }$ ${\displaystyle [\epsilon ]}$ ${\displaystyle [x]}$ ${\displaystyle x\in L}$

В общем случае для любого языка построенный автомат является акцептором автомата состояний . Однако он не обязательно имеет конечное число состояний. Теорема Майхилла–Нерода показывает, что конечность необходима и достаточна для регулярности языка.

Некоторые авторы называют это отношение конгруэнтностью Нерода [ ^{1] [2]} в честь Анила Нерода . ${\displaystyle \sim _{L}}$

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

(1) Если является регулярным. построить минимальный DFA, чтобы принять его. Очевидно, если окажетесь в том же состоянии после прохождения DFA, то , таким образом, число классов эквивалентности не превышает числа состояний DFA, которое должно быть конечным. ${\displaystyle L}$ ${\displaystyle x,y}$ ${\displaystyle x\sim _{L}y}$ ${\displaystyle \sim _{L}}$

Наоборот, если имеет конечное число классов эквивалентности, то построенный в теореме автомат состояний является акцептором DFA, поэтому язык является регулярным. ${\displaystyle \sim _{L}}$

(2) По построению в (1).

(3) Для минимального акцептора DFA мы строим изоморфизм каноническому. ${\displaystyle A}$

Постройте следующее отношение эквивалентности: тогда и только тогда, когда при прохождении через оказываются в одном и том же состоянии . ${\displaystyle x\sim _{A}y}$ ${\displaystyle x,y}$ ${\displaystyle A}$

Так как является акцептором, то если то . Таким образом, каждый класс эквивалентности является объединением одного или нескольких классов эквивалентности . Далее, так как является минимальным, число состояний равно числу классов эквивалентности по части (2). Таким образом . ${\displaystyle A}$ ${\displaystyle x\sim _{A}y}$ ${\displaystyle x\sim _{L}y}$ ${\displaystyle \sim _{L}}$ ${\displaystyle \sim _{A}}$ ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle \sim _{L}}$ ${\displaystyle \sim _{A}=\sim _{L}}$

Теперь это дает нам биекцию между состояниями и состояниями канонического акцептора. Ясно, что эта биекция также сохраняет правила перехода, поэтому она является изоморфизмом DFA. ${\displaystyle A}$

Использование и последствия

Теорема Майхилла –Нерода может быть использована для доказательства регулярности языка путем доказательства того, что число классов эквивалентности конечно. Это может быть сделано с помощью исчерпывающего анализа случаев , в котором, начиная с пустой строки , различающие расширения используются для поиска дополнительных классов эквивалентности до тех пор, пока больше не будет найдено. Например, язык, состоящий из двоичных представлений чисел, которые можно разделить на 3, является регулярным. При пустой строке (или ), и являются различающими расширениями, приводящими к трем классам (соответствующим числам, которые дают остатки 0, 1 и 2 при делении на 3), но после этого шага различающего расширения больше нет. Минимальный автомат, принимающий наш язык, будет иметь три состояния, соответствующие этим трем классам эквивалентности. ${\displaystyle L}$ ${\displaystyle \sim _{L}}$ ${\displaystyle 00}$ ${\displaystyle 11}$ ${\displaystyle 01}$ ${\displaystyle 10}$

Другое непосредственное следствие теоремы заключается в том, что если для языка отношение имеет бесконечно много классов эквивалентности, то оно не является регулярным. Именно это следствие часто используется для доказательства того, что язык не является регулярным. ${\displaystyle L}$ ${\displaystyle \sim _{L}}$

Обобщения

Теорему Майхилла–Нерода можно обобщить на древовидные автоматы . ^[3]

Смотрите также

• Лемма о накачке для регулярных языков , альтернативный метод доказательства того, что язык не является регулярным. Лемма о накачке не всегда может доказать, что язык не является регулярным.
• Синтаксический моноид

Ссылки

1. Бжозовский, Януш ; Шикула, Марек; Йе, Юлий (2018), «Синтаксическая сложность регулярных идеалов», Теория вычислительных систем , 62 (5): 1175–1202, doi : 10.1007/s00224-017-9803-8, hdl : 10012/12499 , S2CID  2238325
2. Crochemore, Maxime и др. (2009), «От конгруэнтности Нерода к суффиксным автоматам с несовпадениями», Теоретическая информатика , 410 (37): 3471–3480, doi : 10.1016/j.tcs.2009.03.011 , S2CID  14277204
3. Хьюберт Комон; Макс Доше; Реми Жилерон; Флоран Жакмар; Денис Лужьес; Кристоф Лёдинг; Софи Тайсон; Марк Томмаси (октябрь 2021 г.). Методы и приложения древовидных автоматов (TATA).Здесь: Раздел 1.5, стр.35-36.

• Хопкрофт, Джон Э .; Ульман, Джеффри Д. (1979), «Глава 3.4», Введение в теорию автоматов, языки и вычисления , Рединг, Массачусетс: Addison-Wesley Publishing, ISBN 0-201-02988-X.
• Нерод, Анил (1958), «Преобразования линейных автоматов», Труды Американского математического общества , 9 (4): 541–544, doi : 10.1090/S0002-9939-1958-0135681-9 , JSTOR  2033204.
• Нерод, Анил; Зауэр, Бертон П. (ноябрь 1957 г.), Фундаментальные концепции теории систем (технический отчет WADC), Центр развития авиации Райта. Документ ASTIA № AD 155741.
• Реган, Кеннет (2007), Заметки о теореме Майхилла-Нерода (PDF) , получено 22.03.2016.

Дальнейшее чтение

• Бахадыр Хуссаинов; Анил Нерод (6 декабря 2012 г.). Теория автоматов и ее применение. Springer Science & Business Media. ISBN 978-1-4612-0171-7.