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

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

Синтаксический коэффициент

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

S\ /\ m=\{u\in M\;\vert \;um\in S\}.

Аналогично, левое частное равно

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

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

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

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

s\sim _{S}t\ \Leftrightarrow \ S\,/\,s\;=\;S\,/\,t\ \Leftrightarrow \ (\forall x\in M\colon \ xs\in S\Leftrightarrow xt\in S)

.

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

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

.

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

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

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

.

Определение распространяется на сравнение, определяемое подмножеством $S$ общего моноида $M$ . – Дизъюнктивное множество это подмножество $S$ такое, что синтаксическое соответствие, определяемое $S$ это отношение равенства. ^[3]

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

[s]_{S}[t]_{S}=[st]_{S}

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

M(S)=M\ /\ {\equiv _{S}}

.

Этот моноид $M(S)$ называется моноидом синтаксическим $S$ .Можно показать, что это наименьший моноид , который распознает $S$ ; то есть, $M(S)$ признает $S$ , и для каждого моноида $N$ признание $S$ , $M(S)$ частным субмоноида является $N$ . Синтаксический моноид $S$ также является перехода минимального автомата моноидом $S$ . ^[1]^[2]^[4]

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

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

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

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

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

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

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

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

Примеры

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

Ссылки

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

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

[Hol160-1] Перейти обратно: ^а ^б Холкомб (1982) стр.160

[Law210-2] Перейти обратно: ^а ^б Лоусон (2004) стр.210

[Law232-3] Лоусон (2004) стр.232

[S55-4] Штраубинг (1994) стр.55

[Sak342-5] Перейти обратно: ^а ^б Сакарович (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] Крошмор, Максим; и др. (2009), «От конгруэнтности Нероде к суффиксным автоматам с несовпадениями», Theoretical Computer Science , 410 (37): 3471–3480, doi : 10.1016/j.tcs.2009.03.011 , S2CID 14277204

[S54-9] Штраубинг (1994) стр.54

[Law211-10] Лоусон (2004), стр. 211-212.

[MP48-11] Перейти обратно: ^а ^б Макнотон, Роберт; Паперт, Сеймур (1971). Автоматы без счетчиков . Научная монография. Том. 65. С приложением Уильяма Хеннемана. МТИ Пресс. п. 48 . ISBN 0-262-13076-9 . Збл 0232.94024 .

[Law233-12] Лоусон (2004) стр.233

[13] Марсель-Поль Шютценбергер (1965). «О конечных моноидах, имеющих только тривиальные подгруппы» (PDF) . Информация и вычисления . 8 (2): 190–194. дои : 10.1016/s0019-9958(65)90108-7 .

[S60-14] Штраубинг (1994) стр.60

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]