Синтаксический моноид - Syntactic monoid

В математике и информатике , то синтаксический Моноид из формального языка является наименьшим Моноид , что признает язык . ${\ Displaystyle M (L)}$ ${\ displaystyle L}$${\ displaystyle L}$

Синтаксическое частное

Свободный моноид на заданный наборе является моноидом, элементы которого являются все строками из нуля или более элементов из этого набора, с конкатенацией как моноидная операция и пустой строкой в качестве единичного элемента . Учитывая подмножество свободного моноида , можно определить множества, которые состоят из формальных левых или правых обратных элементов в . Они называются частными , и можно определить правые или левые частные, в зависимости от того, с какой стороны происходит конкатенация. Таким образом, правое частное от элемента из - это множество ${\ displaystyle S}$${\ displaystyle M}$${\ displaystyle S}$${\ displaystyle S}$${\ displaystyle m}$${\ displaystyle M}$

${\ Displaystyle S \ / \ m = \ {u \ in M ​​\; \ vert \; мм \ in S \}.}$

Точно так же левое частное равно

${\ displaystyle m \ setminus S = \ {u \ in M ​​\; \ vert \; mu \ in S \}.}$

Синтаксическая эквивалентность

Синтаксический фактор индуцирует отношение эквивалентности на , называется синтаксическое отношением , или синтаксической эквивалентность (индуцированной ). ${\ displaystyle M}$${\ displaystyle S}$

Право синтаксической эквивалентности является отношением эквивалентности

${\ Displaystyle s \ sim _ {S} t \ \ Leftrightarrow \ S \, / \, s \; = \; S \, / \, t \ \ Leftrightarrow \ (\ forall x \ in M ​​\ двоеточие \ xs \ в S \ Leftrightarrow xt \ in S)}$.

Аналогичным образом , влево синтаксической эквивалентности является

${\ displaystyle s \; {} _ {S} {\ sim} \; t \ \ Leftrightarrow \ s \ setminus S \; = \; t \ setminus S \ \ Leftrightarrow \ (\ forall y \ in M ​​\ двоеточие \ sy \ in S \ Leftrightarrow ty \ in S)}$.

Заметьте, что правая синтаксическая эквивалентность - это левая конгруэнтность относительно конкатенации строк и наоборот; т.е. для всех . ${\ Displaystyle s \ sim _ {S} т \ \ Rightarrow \ xs \ sim _ {S} xt \}$${\ displaystyle x \ in M}$

Синтаксической конгруэнции или Myhill конгруэнтность определяется как

${\ Displaystyle s \ Equiv _ {S} t \ \ Leftrightarrow \ (\ forall x, y \ in M ​​\ двоеточие \ xsy \ in S \ Leftrightarrow xty \ in S)}$.

Определение распространяется на сравнение, определяемое подмножеством общего моноида . Дизъюнктивное множество является подмножеством таким образом, что синтаксическая конгруэнтность определяется этим отношение равенства. ${\ displaystyle S}$${\ displaystyle M}$${\ displaystyle S}$${\ displaystyle S}$

Назовем класс эквивалентности синтаксической конгруэнтности. Синтаксическая конгруэнтность совместима с конкатенацией в моноиде в том смысле, что ${\ displaystyle [s] _ {S}}$${\ displaystyle s}$

${\ displaystyle [s] _ {S} [t] _ {S} = [st] _ {S}}$

для всех . Таким образом, синтаксическое частное является морфизмом моноида и индуцирует частный моноид${\ displaystyle s, t \ in M}$

${\ Displaystyle М (S) = М \ / \ {\ эквив _ {S}}}$.

Это Моноид называется синтаксической моноид из . Можно показать, что распознает наименьший моноид ; то есть, признает , и для каждых Моноид признания , является фактором в подмоноиде из . Синтаксический Моноид также переход Моноид от минимального автомата из . ${\ Displaystyle M (S)}$${\ displaystyle S}$ ${\ displaystyle S}$${\ Displaystyle M (S)}$${\ displaystyle S}$${\ displaystyle N}$${\ displaystyle S}$${\ Displaystyle M (S)}$${\ displaystyle N}$${\ displaystyle S}$${\ displaystyle S}$

Языковая группа является один , для которых синтаксический моноид в группу .

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

Теорема Майхилла – Нероде утверждает: язык является регулярным тогда и только тогда, когда семейство частных конечно, или, что то же самое, левая синтаксическая эквивалентность имеет конечный индекс (то есть он разбивается на конечное число классов эквивалентности). ${\ displaystyle L}$${\ Displaystyle \ {м \ setminus L \, \ vert \; м \ в М \}}$${\ displaystyle {} _ {S} {\ sim}}$${\ displaystyle M}$

Эта теорема была впервые доказана Анилом Нероде ( Nerode, 1958 ), поэтому некоторые авторы называют это соотношение конгруэнцией Нероде . ${\ displaystyle {} _ {S} {\ sim}}$

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

Доказательство части «только если» состоит в следующем. Предположим, что распознающий конечный автомат считывает ввод, который приводит к состоянию . Если это другая строка, прочитанная машиной, которая также завершается в том же состоянии , то очевидно, что она есть . Таким образом, количество элементов в не более чем равно количеству состояний автомата и не более чем количеству конечных состояний. ${\ displaystyle L}$${\ displaystyle x}$${\ displaystyle p}$${\ displaystyle y}$${\ displaystyle p}$${\ Displaystyle х \ setminus L \, = y \ setminus L}$${\ Displaystyle \ {м \ setminus L \, \ vert \; м \ в М \}}$${\ Displaystyle \ {м \ setminus L \, \ vert \; м \ in L \}}$

Для доказательства части «если» предположим, что число элементов в конечно. Затем можно построить автомат, где - множество состояний, - множество конечных состояний, язык - начальное состояние, а функция перехода задается выражением . Ясно, что этот автомат распознает . Таким образом, язык узнаваем тогда и только тогда, когда множество конечно. Обратите внимание, что это доказательство также строит минимальный автомат. ${\ Displaystyle \ {м \ setminus L \, \ vert \; м \ в М \}}$${\ Displaystyle Q = \ {м \ setminus L \, \ vert \; м \ в М \}}$${\ Displaystyle F = \ {м \ setminus L \, \ vert \; м \ in L \}}$${\ displaystyle L}$${\ Displaystyle у \ setminus (х \ setminus L) = (ху) \ setminus L}$${\ displaystyle L}$${\ displaystyle L}$${\ Displaystyle \ {м \ setminus L \, \ vert \; м \ в М \}}$

Примеры

• Позвольте быть языком слов четной длины. Синтаксическое сравнение имеет два класса: само слово и слова нечетной длины. Синтаксический моноид - это группа порядка 2 на .${\ displaystyle L}$${\ Displaystyle А = \ {а, Ь \}}$${\ displaystyle L}$${\ displaystyle L_ {1}}$${\ Displaystyle \ {L, L_ {1} \}}$
• Бициклический моноид является синтаксическим Моноидом на языке Дейка (язык сбалансированных наборов скобок).
• Свободный моноид на (где ) является синтаксическим Моноидом языка , где есть реверсирование слова .${\ displaystyle A}$${\ Displaystyle \ влево | А \ вправо |> 1}$${\ Displaystyle \ {ww ^ {R} \ mid w \ in A ^ {*} \}}$${\ displaystyle w ^ {R}}$${\ displaystyle w}$
• Каждый конечный моноид гомоморфен синтаксическому моноиду некоторого нетривиального языка, но не каждый конечный моноид изоморфен синтаксическому моноиду.
• Каждая конечная группа изоморфна синтаксическому моноиду некоторого нетривиального языка.
• Язык, в котором число вхождений и конгруэнтно по модулю, является групповым языком с синтаксическим моноидом .${\ Displaystyle \ {а, б \}}$${\ displaystyle a}$${\ displaystyle b}$${\ displaystyle 2 ^ {n}}$${\ Displaystyle \ mathbb {Z} / 2 ^ {п} \ mathbb {Z}}$
• Моноиды трассировки являются примерами синтаксических моноидов.
• Марсель-Пауль Шютценбергер охарактеризовал языки без звезд как языки с конечными апериодическими синтаксическими моноидами.

Рекомендации

• Андерсон, Джеймс А. (2006). Теория автоматов в современных приложениях . При участии Тома Хеда. Кембридж: Издательство Кембриджского университета . ISBN 0-521-61324-8. Zbl  1127.68049 .
• Холкомб, WML (1982). Теория алгебраических автоматов . Кембриджские исследования в области высшей математики. 1 . Издательство Кембриджского университета . ISBN 0-521-60492-3. Zbl  0489.68046 .
• Лоусон, Марк В. (2004). Конечные автоматы . Чепмен и Холл / CRC. ISBN 1-58488-255-7. Zbl  1086.68074 .
• Пин, Жан-Эрик (1997). «10. Синтаксические полугруппы». В Розенберге, G .; Саломаа, А. (ред.). Справочник по теории формального языка (PDF) . 1 . Springer-Verlag . С. 679–746. Zbl  0866.68057 .
• Сакарович, Жак (2009). Элементы теории автоматов . Перевод с французского Рувима Томаса. Издательство Кембриджского университета . ISBN 978-0-521-84425-3. Zbl  1188.68177 .
• Штраубинг, Ховард (1994). Конечные автоматы, формальная логика и сложность схем . Успехи теоретической информатики. Базель: Биркхойзер. ISBN 3-7643-3719-2. Zbl  0816.68086 .