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

Наименьший моноид, распознающий формальный язык

В математике и информатике синтаксический моноид формального языка — это наименьший моноид , распознающий язык . ${\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 \;um\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\colon \ xs\in S\Leftrightarrow xt\in S)}$.

Аналогично, левая синтаксическая эквивалентность :

${\displaystyle s\;{}_{S}{\sim }\;t\ \Leftrightarrow \ s\setminus S\;=\;t\setminus S\ \Leftrightarrow \ (\forall y\in M\colon \ sy\in S\Leftrightarrow ty\in S)}$.

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

Синтаксическая конгруэнтность или конгруэнтность Майхилла ^[1] определяется как ^[2]

${\displaystyle s\equiv _{S}t\ \Leftrightarrow \ (\forall x,y\in M\colon \ xsy\in S\Leftrightarrow xty\in S)}$.

Определение распространяется на конгруэнтность, определяемую подмножеством общего моноида . Дизъюнктивное множество — это подмножество , такое, что синтаксическая конгруэнтность, определяемая отношением, является отношением равенства. ^[3] ${\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 M(S)=M\ /\ {\equiv _{S}}}$.

Этот моноид называется синтаксическим моноидом . Можно показать, что это наименьший моноид , который распознаёт ; то есть распознаёт , и для каждого моноида, распознающего , является частным подмоноида . Синтаксический моноид также является моноидом перехода минимального автомата . ^{[1] [2] [4]} ${\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}$

Групповой язык — это язык, для которого синтаксический моноид является группой . ^[5]

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

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

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

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

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

Для доказательства части "if" предположим, что число элементов в конечно. Тогда можно построить автомат, где — множество состояний, — множество конечных состояний, язык — начальное состояние, а функция перехода задается как . Очевидно, этот автомат распознает . ${\displaystyle \{m\setminus L\,\vert \;m\in M\}}$ ${\displaystyle Q=\{m\setminus L\,\vert \;m\in M\}}$ ${\displaystyle F=\{m\setminus L\,\vert \;m\in L\}}$ ${\displaystyle L}$ ${\displaystyle \delta _{y}\colon x\setminus L\to y\setminus (x\setminus L)=(xy)\setminus L}$ ${\displaystyle L}$

Таким образом, язык узнаваем тогда и только тогда, когда множество конечно. Обратите внимание, что это доказательство также строит минимальный автомат. ${\displaystyle L}$ ${\displaystyle \{m\setminus L\,\vert \;m\in M\}}$

Примеры

• Пусть будет языком над словами четной длины. Синтаксическая конгруэнтность имеет два класса, себя и , слова нечетной длины. Синтаксический моноид — это группа порядка 2 на . ^[9] ${\displaystyle L}$ ${\displaystyle A=\{a,b\}}$ ${\displaystyle L}$ ${\displaystyle L_{1}}$ ${\displaystyle \{L,L_{1}\}}$
• Для языка минимальный автомат имеет 4 состояния, а синтаксический моноид имеет 15 элементов. ^[10] ${\displaystyle (ab+ba)^{*}}$
• Бициклический моноид — это синтаксический моноид языка Дика (языка сбалансированных наборов скобок).
• Свободный моноид на (где ) является синтаксическим моноидом языка , где — перестановка слова . (Для , можно использовать язык квадратных степеней буквы.) ${\displaystyle A}$ ${\displaystyle \left|A\right|>1}$ ${\displaystyle \{ww^{R}\mid w\in A^{*}\}}$ ${\displaystyle w^{R}}$ ${\displaystyle w}$ ${\displaystyle \left|A\right|=1}$
• Каждый нетривиальный конечный моноид гомоморфен ^{[ требуется пояснение ]} синтаксическому моноиду некоторого нетривиального языка, ^[11] но не каждый конечный моноид изоморфен синтаксическому моноиду. ^[12]
• Каждая конечная группа изоморфна синтаксическому моноиду некоторого регулярного языка. ^[11]
• Язык , в котором число вхождений и сравнимо по модулю, является групповым языком с синтаксическим моноидом . ^[5] ${\displaystyle \{a,b\}}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle 2^{n}}$ ${\displaystyle \mathbb {Z} /2^{n}\mathbb {Z} }$
• Примерами синтаксических моноидов являются трассовые моноиды .
• Марсель-Пауль Шютценбергер ^[13] охарактеризовал языки без звезд как языки с конечными апериодическими синтаксическими моноидами. ^[14]

Ссылки

1. Holcombe (1982) стр.160
2. Lawson (2004) стр.210
3. Лоусон (2004) стр.232
4. Штраубинг (1994) стр.55
5. Sakarovitch (2009) стр.342
6. Нерод, Анил (1958), «Преобразования линейных автоматов», Труды Американского математического общества , 9 (4): 541–544, doi : 10.1090/S0002-9939-1958-0135681-9 , JSTOR  2033204
7. Бжозовский, Януш; Шикула, Марек; Йе, Юлий (2018), «Синтаксическая сложность регулярных идеалов», Теория вычислительных систем , 62 (5): 1175–1202, doi : 10.1007/s00224-017-9803-8, hdl : 10012/12499 , S2CID  2238325
8. Crochemore, Maxime и др. (2009), «От конгруэнтности Нерода к суффиксным автоматам с несовпадениями», Теоретическая информатика , 410 (37): 3471–3480, doi : 10.1016/j.tcs.2009.03.011 , S2CID  14277204
9. Штраубинг (1994) стр.54
10. Лоусон (2004) стр.211-212
11. McNaughton, Robert; Papert, Seymour (1971). Counter-free Automata . Исследовательская монография. Том 65. С приложением Уильяма Хеннемана. MIT Press. стр. 48. ISBN 0-262-13076-9. Збл  0232.94024.
12. Лоусон (2004) стр.233
13. Марсель-Пауль Шютценбергер (1965). «О конечных моноидах, имеющих только тривиальные подгруппы» (PDF) . Информация и вычисления . 8 (2): 190–194. doi : 10.1016/s0019-9958(65)90108-7 .
14. Штраубинг (1994) стр.60

• Андерсон, Джеймс А. (2006). Теория автоматов с современными приложениями . С участием Тома Хэда. Кембридж: Cambridge University Press . ISBN 0-521-61324-8. Збл  1127.68049.
• Холкомб, В. М. Л. (1982). Алгебраическая теория автоматов . Кембриджские исследования по высшей математике. Том 1. Cambridge University Press . ISBN 0-521-60492-3. Збл  0489.68046.
• Лоусон, Марк В. (2004). Конечные автоматы . Чепмен и Холл/CRC. ISBN 1-58488-255-7. Збл  1086.68074.
• Pin, Jean-Éric (1997). "10. Синтаксические полугруппы". В Rozenberg, G.; Salomaa, A. (ред.). Handbook of Formal Language Theory (PDF) . Том 1. Springer-Verlag . С. 679–746. Zbl  0866.68057.
• Сакарович, Жак (2009). Элементы теории автоматов . Перевод с французского Рубена Томаса. Cambridge University Press . ISBN 978-0-521-84425-3. Збл  1188.68177.
• Straubing, Howard (1994). Конечные автоматы, формальная логика и сложность схем . Прогресс в теоретической информатике. Базель: Birkhäuser. ISBN 3-7643-3719-2. Збл  0816.68086.