Введение

Наименьший моноид, распознающий формальный язык. В математике и информатике синтаксический моноид формального языка — это наименьший моноид, распознающий этот язык.

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

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

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

Доказательство части "только если" выглядит следующим образом. Предположим, что конечный автомат, распознающий язык, читает входную строку , которая приводит к состоянию . Если другая строка, читаемая машиной, также заканчивается в том же состоянии , то, очевидно, у них есть общий суффикс . Таким образом, количество элементов в множестве не превышает количество состояний автомата, а количество элементов в не превышает количество конечных состояний. Для доказательства части "если", предположим, что множество конечно. Тогда можно построить автомат, где является множеством состояний, – множеством конечных состояний, – начальным состоянием, а функция перехода задается следующим образом: . Очевидно, этот автомат распознает язык .

Таким образом, язык распознаваем тогда и только тогда, когда множество конечно. Обратите внимание, что это доказательство также строит минимальный автомат.

Примеры

Пусть L – язык над Σ, состоящий из слов четной длины. Синтаксическая конгруэнтность имеет два класса: сам L и L', слова нечетной длины. Синтаксический моноид – это группа порядка 2 на L. Для языка L минимальный автомат имеет 4 состояния, а синтаксический моноид содержит 15 элементов. Бициклический моноид является синтаксическим моноидом языка Дайка (язык сбалансированных скобок). Свободный моноид на Σ (где Σ – алфавит) является синтаксическим моноидом языка L, где w → wR (wR – это обращение слова w). (Для Σ, состоящего из одной буквы, можно использовать язык квадратных степеней этой буквы). Каждый нетривиальный конечный моноид гомоморфен синтаксическому моноиду некоторого нетривиального языка, но не каждый конечный моноид изоморфен синтаксическому моноиду. Каждая конечная группа изоморфна синтаксическому моноиду некоторого регулярного языка. Языки, свободные от звёзд, характеризуются как те, у которых конечные апериодические синтаксические моноиды.