Синтаксический моноид
В математике и информатике синтаксический моноид формального языка это наименьший моноид , распознающий язык .
Синтаксический фактор [ править ]
Свободный моноид в заданном наборе — это моноид, элементами которого являются все строки из нуля или более элементов из этого набора, с конкатенацией строк в качестве операции моноида и пустой строкой в качестве единичного элемента . Учитывая подмножество свободного моноида , можно определить множества, состоящие из формальных левых или правых обратных элементов в . Они называются частными , и можно определить правые или левые частные, в зависимости от того, какую сторону они объединяют. Таким образом, правильное частное по элементу от это набор
Аналогично, левое частное равно
Синтаксическая эквивалентность [ править ]
Синтаксический коэффициент [ нужны разъяснения ] индуцирует отношение эквивалентности на , называемое синтаксическим отношением или синтаксической эквивалентностью (индуцированной ).
Правильная синтаксическая эквивалентность – это отношение эквивалентности
- .
Аналогично, левая синтаксическая эквивалентность равна
- .
Обратите внимание, что правая синтаксическая эквивалентность является левой конгруэнцией относительно конкатенации строк и наоборот; то есть, для всех .
Синтаксическое соответствие или Майхилла соответствие [1] определяется как [2]
- .
Определение распространяется на сравнение, определяемое подмножеством общего моноида . – Дизъюнктивное множество это подмножество такое, что синтаксическое соответствие, определяемое это отношение равенства. [3]
Давайте позвоним класс эквивалентности для синтаксического соответствия.Синтаксическое соответствие совместимо с конкатенацией в моноиде, поскольку оно имеет
для всех . Таким образом, синтаксический фактор является морфизмом моноида и индуцирует фактормоноид
- .
Этот моноид называется моноидом синтаксическим .Можно показать, что это наименьший моноид , распознающий ; то есть, признает , и для каждого моноида признание , частным субмоноида является . Синтаксический моноид также является перехода минимального автомата моноидом . [1] [2] [4]
Групповой язык — это язык, для которого синтаксический моноид является группой . [5]
- Теорема Нерода Майхилла
Теорема Майхилла-Нерода гласит: язык регулярно тогда и только тогда, когда семейство частных конечна или, что то же самое, левая синтаксическая эквивалентность имеет конечный индекс (то есть разделяет на конечное число классов эквивалентности). [6]
Эта теорема была впервые доказана Анилом Нероде ( Nerode 1958 ) и соотношение называют его конгруэнтностью Нерода . поэтому некоторые авторы [7] [8]
Доказательство [ править ]
Доказательство части «только если» состоит в следующем. Предположим, что конечный автомат, распознающий читает ввод , что приводит к состоянию . Если это еще одна строка, читаемая машиной, также заканчивающаяся в том же состоянии , то, очевидно, имеется . Таким образом, количество элементов в не более чем равно числу состояний автомата и не более чем число конечных состояний.
Для доказательства части «если» предположим, что количество элементов в конечно. Тогда можно построить автомат, в котором это набор состояний, — это набор конечных состояний, язык — начальное состояние, а функция перехода определяется выражением . Очевидно, этот автомат распознает .
Таким образом, язык распознаваем тогда и только тогда, когда множество конечно. Обратите внимание, что это доказательство также строит минимальный автомат.
Примеры [ править ]
- Позволять быть языком оконченным слов четной длины. Синтаксическое соответствие имеет два класса: себя и , слова нечетной длины. Синтаксический моноид – это группа порядка 2 на . [9]
- Для языка , минимальный автомат имеет 4 состояния, а синтаксический моноид — 15 элементов. [10]
- Бициклический моноид — это синтаксический моноид языка Дика (языка сбалансированных наборов скобок).
- Бесплатный моноид на (где ) — синтаксический моноид языка , где это перестановка слова . (Для , можно использовать язык квадратичных степеней буквы.)
- Любой нетривиальный конечный моноид гомоморфен. [ нужны разъяснения ] синтаксическому моноиду некоторого нетривиального языка, [11] но не всякий конечный моноид изоморфен синтаксическому моноиду. [12]
- Любая конечная группа изоморфна синтаксическому моноиду некоторого регулярного языка. [11]
- Язык закончился в котором количество появлений и конгруэнтны по модулю это групповой язык с синтаксическим моноидом . [5]
- Моноиды трассировки являются примерами синтаксических моноидов.
- Марсель-Поль Шютценбергер [13] охарактеризовал беззвездные языки как языки с конечными апериодическими синтаксическими моноидами. [14]
Ссылки [ править ]
- ^ Jump up to: Перейти обратно: а б Холкомб (1982) стр.160
- ^ Jump up to: Перейти обратно: а б Лоусон (2004) стр.210
- ^ Лоусон (2004) стр.232
- ^ Штраубинг (1994) стр.55
- ^ Jump up to: Перейти обратно: а б Сакарович (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.
- ^ Jump up to: Перейти обратно: а б Макнотон, Роберт; Паперт, Сеймур (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 .