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

В математике и информатике , то синтаксический моноиде M ( L ) из формального языка L является наименьшим Моноид , что распознает язык 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 \}.}$

Синтаксическая эквивалентность [ править ]

Синтаксический фактор индуцирует отношение эквивалентности на M , называемое синтаксическим отношением , или синтаксической эквивалентностью (индуцированное S ). Правая синтаксическая эквивалентность - это отношение эквивалентности

${\ Displaystyle \ sim _ {S} \; = \ {(s, t) \ in M ​​\ times M \, \ vert \; S \ / \ s = S \ / \ t \}.}$

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

${\displaystyle {}_{S}{\sim }\,=\{(s,t)\in M\times M\,\vert \;s\setminus S=t\setminus S\}.}$

Синтаксической конгруэнции или Myhill конгруэнции ^[1] может быть определено как ^[2]

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

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

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

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

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

${\displaystyle M(S)=M\ /\ {\equiv _{S}}.}$

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

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

${\displaystyle \{m\setminus L\,\vert \;m\in M\}}$

конечно. ^[1] Доказательство части «только если» состоит в следующем. Предположим, что распознающий конечный автомат считывает вход x, который приводит к состоянию p . Если y - это другая строка, прочитанная машиной, которая также завершается в том же состоянии p , то очевидно, что это так . Таким образом, количество элементов в не более чем равно количеству состояний автомата и не более чем количеству конечных состояний. Для доказательства части «если» предположим, что число элементов в конечно. Затем можно построить автомат, где - множество состояний, - множество конечных состояний, язык L${\displaystyle L}$${\displaystyle x\setminus L\,=y\setminus L}$${\displaystyle \{m\setminus L\,\vert \;m\in M\}}$${\displaystyle \{m\setminus L\,\vert \;m\in L\}}$${\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\}}$- начальное состояние, а функция перехода определяется выражением . Очевидно, что этот автомат распознает L . Таким образом, язык L узнаваем тогда и только тогда, когда множество конечно. Обратите внимание, что это доказательство также строит минимальный автомат.${\displaystyle y\setminus (x\setminus L)=(xy)\setminus L}$${\displaystyle \{m\setminus L\,\vert \;m\in M\}}$

Учитывая регулярное выражение E , представляющее S , то легко вычислить синтаксический моноид S .

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

Примеры [ править ]

• Пусть L - язык над A = { a , b } слов четной длины. Синтаксическая конгруэнтность имеет два класса: собственно L и L ₁ , слова нечетной длины. Синтаксический моноид - это группа порядка 2 на { L , L ₁ }. ^[6]
• Бициклический моноид является синтаксическим Моноидом на языке Дейка (язык сбалансированных наборов скобок).
• Свободный моноид на А (| |> 1) является синтаксическим Моноидом языка { жв ^R | w в A *}, где w ^R обозначает обращение слова w .
• Каждый конечный моноид гомоморфен ^{[ требуется пояснение ]} синтаксическому моноиду некоторого нетривиального языка ^[7], но не каждый конечный моноид изоморфен синтаксическому моноиду. ^[8]
• Каждая конечная группа изоморфна синтаксическому моноиду некоторого нетривиального языка. ^[7]
• Язык над { a , b }, в котором число вхождений a и b конгруэнтно по модулю 2 ^n, является групповым языком с синтаксическим моноидом Z / 2 ⁿ . ^[5]
• Моноиды трассировки являются примерами синтаксических моноидов.
• Марсель-Пауль Шютценбергер ^[9] охарактеризовал языки без звезд как языки с конечными апериодическими синтаксическими моноидами. ^[10]

Ссылки [ править ]

• Андерсон, Джеймс А. (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 .