В математике и информатике , то синтаксический моноиде M ( L ) из формального языка L является наименьшим Моноид , что распознает язык L .
Синтаксическое частное
Свободный моноид на заданный наборе является моноидом, элементы которого являются все строками из нуля или более элементов из этого набора, с конкатенацией как моноидная операция и пустой строкой в качестве единичного элемента . Учитывая подмножество свободного моноида , можно определить множества, которые состоят из формальных левых или правых обратных элементов в. Они называются частными , и можно определить правые или левые частные, в зависимости от того, с какой стороны происходит конкатенация. Таким образом, правое частное от элементом из это набор
Точно так же левое частное равно
Синтаксическая эквивалентность
Синтаксический фактор индуцирует отношение эквивалентности на M , называемое синтаксическим отношением , или синтаксической эквивалентностью (индуцированное S ). Правая синтаксическая эквивалентность - это отношение эквивалентности
Точно так же левое синтаксическое отношение
Синтаксической конгруэнции или Myhill конгруэнции [1] может быть определено как [2]
Определение продолжается до конгруэнции , определяемого подмножество S общего моноидного M . Дизъюнктивное множество является подмножество S таким образом, что синтаксическая конгруэнтность определяется S есть отношение равенства. [3]
Позвольте нам позвонить класс эквивалентности для синтаксической конгруэнтности. Синтаксическая конгруэнтность совместима с конкатенацией в моноиде в том смысле, что
для всех . Таким образом, синтаксическое частное является морфизмом моноида и индуцирует частный моноид
Этот моноид называется синтаксической моноид из S . Можно показать, что это наименьший моноид, который распознает S ; то есть, М ( S ) распознает S , и для каждого моноиде N распознающего S , M ( S ) представляет собой частное от деления на подмоноид из N . Синтаксическое моноид S также является переход моноид от минимального автомата из S . [1] [2] [4]
Точно так же язык L является регулярным тогда и только тогда, когда семейство частных
конечно. [1] Доказательство части «только если» состоит в следующем. Предположим, что конечный автомат, распознающийчитает ввод x, который приводит к состоянию p . Если y - это другая строка, прочитанная машиной, которая также завершается в том же состоянии p , то очевидно, что одна строка. Таким образом, количество элементов в не более чем равно количеству состояний автомата и не более чем количество конечных состояний. Для доказательства части «если» предположим, что количество элементов вконечно. Тогда можно построить автомат, в котором это множество состояний, - набор конечных состояний, язык L - начальное состояние, а функция перехода задается выражением. Очевидно, что этот автомат распознает L . Таким образом, язык L узнаваем тогда и только тогда, когда множествоконечно. Обратите внимание, что это доказательство также строит минимальный автомат.
Учитывая регулярное выражение E , представляющее S , то легко вычислить синтаксический моноид S .
Языковая группа является один , для которых синтаксический моноид в группу . [5]
Примеры
- Пусть L - язык над A = { a , b } слов четной длины. Синтаксическая конгруэнтность имеет два класса: собственно L и L 1 , слова нечетной длины. Синтаксический моноид - это группа порядка 2 на { L , L 1 }. [6]
- Бициклический моноид является синтаксическим Моноидом на языке Дейка (язык сбалансированных наборов скобок).
- Свободный моноид на А (| |> 1) является синтаксическим Моноидом языка { жв R | w в A *}, где w R обозначает обращение слова w .
- Каждый конечный моноид гомоморфен [ требуется пояснение ] синтаксическому моноиду некоторого нетривиального языка [7], но не каждый конечный моноид изоморфен синтаксическому моноиду. [8]
- Каждая конечная группа изоморфна синтаксическому моноиду некоторого нетривиального языка. [7]
- Язык над { a , b }, в котором число вхождений a и b конгруэнтно по модулю 2 n, является групповым языком с синтаксическим моноидом Z / 2 n . [5]
- Моноиды трассировки являются примерами синтаксических моноидов.
- Марсель-Пауль Шютценбергер [9] охарактеризовал языки без звезд как языки с конечными апериодическими синтаксическими моноидами. [10]
Рекомендации
- ^ a b c Холкомб (1982) с.160
- ^ a b Лоусон (2004) стр.210
- ^ Лоусон (2004) стр.232
- ^ Штраубинг (1994) с.55
- ^ a b Сакарович (2009) с.342
- Перейти ↑ Straubing (1994) p.54
- ^ а б Макнотон, Роберт; Паперт, Сеймур (1971). Автоматы без счетчиков . Монография исследований. 65 . С приложением Уильяма Хеннемана. MIT Press. п. 48 . ISBN 0-262-13076-9. Zbl 0232.94024 .
- ^ Lawson (2004) p.233
- ^ Марсель-Пауль Шютценбергер (1965). «О конечных моноидах, имеющих только тривиальные подгруппы» (PDF) . Информация и вычисления . 8 (2): 190–194. DOI : 10.1016 / s0019-9958 (65) 90108-7 .
- ^ Штраубинг (1994) стр.60
- Андерсон, Джеймс А. (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 .