Jump to content

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

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

Синтаксический фактор [ править ]

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

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

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

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

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

.

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

.

Обратите внимание, что правая синтаксическая эквивалентность является левой конгруэнцией относительно конкатенации строк и наоборот; то есть, для всех .

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

.

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

Давайте позвоним класс эквивалентности для синтаксического соответствия.Синтаксическое соответствие совместимо с конкатенацией в моноиде, поскольку оно имеет

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

.

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

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

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

Теорема Майхилла-Нерода гласит: язык регулярно тогда и только тогда, когда семейство частных конечна или, что то же самое, левая синтаксическая эквивалентность имеет конечный индекс (то есть разделяет на конечное число классов эквивалентности). [6]

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

Доказательство [ править ]

Доказательство части «только если» состоит в следующем. Предположим, что конечный автомат, распознающий читает ввод , что приводит к состоянию . Если это еще одна строка, читаемая машиной, также заканчивающаяся в том же состоянии , то, очевидно, имеется . Таким образом, количество элементов в не более чем равно числу состояний автомата и не более чем число конечных состояний.

Для доказательства части «если» предположим, что количество элементов в конечно. Тогда можно построить автомат, в котором это набор состояний, — это набор конечных состояний, язык — начальное состояние, а функция перехода определяется выражением . Очевидно, этот автомат распознает .

Таким образом, язык распознаваем тогда и только тогда, когда множество конечно. Обратите внимание, что это доказательство также строит минимальный автомат.

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

  • Позволять быть языком оконченным слов четной длины. Синтаксическое соответствие имеет два класса: себя и , слова нечетной длины. Синтаксический моноид – это группа порядка 2 на . [9]
  • Для языка , минимальный автомат имеет 4 состояния, а синтаксический моноид — 15 элементов. [10]
  • Бициклический моноид — это синтаксический моноид языка Дика (языка сбалансированных наборов скобок).
  • Бесплатный моноид на (где ) — синтаксический моноид языка , где это перестановка слова . (Для , можно использовать язык квадратичных степеней буквы.)
  • Любой нетривиальный конечный моноид гомоморфен. [ нужны разъяснения ] синтаксическому моноиду некоторого нетривиального языка, [11] но не всякий конечный моноид изоморфен синтаксическому моноиду. [12]
  • Любая конечная группа изоморфна синтаксическому моноиду некоторого регулярного языка. [11]
  • Язык закончился в котором количество появлений и конгруэнтны по модулю это групповой язык с синтаксическим моноидом . [5]
  • Моноиды трассировки являются примерами синтаксических моноидов.
  • Марсель-Поль Шютценбергер [13] охарактеризовал беззвездные языки как языки с конечными апериодическими синтаксическими моноидами. [14]

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

  1. ^ Jump up to: Перейти обратно: а б Холкомб (1982) стр.160
  2. ^ Jump up to: Перейти обратно: а б Лоусон (2004) стр.210
  3. ^ Лоусон (2004) стр.232
  4. ^ Штраубинг (1994) стр.55
  5. ^ Jump up to: Перейти обратно: а б Сакарович (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
  9. ^ Штраубинг (1994) стр.54
  10. ^ Лоусон (2004), стр. 211-212.
  11. ^ Jump up to: Перейти обратно: а б Макнотон, Роберт; Паперт, Сеймур (1971). Автоматы без счетчиков . Научная монография. Том. 65. С приложением Уильяма Хеннемана. МТИ Пресс. п. 48 . ISBN  0-262-13076-9 . Збл   0232.94024 .
  12. ^ Лоусон (2004) стр.233
  13. ^ Марсель-Поль Шютценбергер (1965). «О конечных моноидах, имеющих только тривиальные подгруппы» (PDF) . Информация и вычисления . 8 (2): 190–194. дои : 10.1016/s0019-9958(65)90108-7 .
  14. ^ Штраубинг (1994) стр.60
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: a14f826370f9da7187a1418ac8f09622__1718123460
URL1:https://arc.ask3.ru/arc/aa/a1/22/a14f826370f9da7187a1418ac8f09622.html
Заголовок, (Title) документа по адресу, URL1:
Syntactic monoid - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)