Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

Регулярный язык называется звезда свободного , если она может быть описана регулярным выражением , составленным из букв алфавита , от пустого множества символов, всех логических операторов - в том числе комплементарности - и конкатенации , но не Клини звезды . [1] Так , например, на языке слов в алфавите , которые не имеют последовательных элементов а может быть определена , где обозначает дополнение подмножества из . Это условие эквивалентно нулевой высоте обобщенной звезды .

Примером обычного языка, не отмеченного звездочкой, является . [2]

Марсель-Пауль Шютценбергер охарактеризовал языки без звезд как языки с апериодическими синтаксическими моноидами . [3] [4] Их также можно логически охарактеризовать как языки, определяемые в FO [<], логике первого порядка над натуральными числами с отношением «меньше чем», [5] как языки без счетчиков [6] и как языки, определяемые в линейной темпоральной логике . [7]

Все языки без звездочек находятся в унифицированном AC 0 .

См. Также [ править ]

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

  1. ↑ Лоусон (2004), стр.235
  2. ↑ Арто Саломаа (1981). Драгоценности теории формального языка . Computer Science Press. п. 53. ISBN 978-0-914894-69-8.
  3. ↑ Марсель-Пауль Шютценбергер (1965). «О конечных моноидах, имеющих только тривиальные подгруппы» (PDF) . Информация и вычисления . 8 (2): 190–194. DOI : 10.1016 / s0019-9958 (65) 90108-7 .
  4. ^ Lawson (2004) p.262
  5. ^ Straubing, Ховард (1994). Конечные автоматы, формальная логика и сложность схем . Успехи теоретической информатики. Базель: Биркхойзер. п. 79 . ISBN 3-7643-3719-2. Zbl  0816.68086 .
  6. ^ Макнотон, Роберт; Паперт, Сеймур (1971). Автоматы без счетчиков . Монография исследований. 65 . С приложением Уильяма Хеннемана. MIT Press. ISBN 0-262-13076-9. Zbl  0232.94024 .
  7. ^ Камп, Йохан Энтони Виллем (1968). Напряженная логика и теория линейного порядка . Калифорнийский университет в Лос-Анджелесе (UCLA).
  • Лоусон, Марк В. (2004). Конечные автоматы . Чепмен и Холл / CRC. ISBN 1-58488-255-7. Zbl  1086.68074 .
  • Дикерт, Фолькер; Гастин, Пол (2008). «Определимые языки первого порядка». В Йорге Флуме; Эрих Гредель; Томас Уилке (ред.). Логика и автоматы: история и перспективы (PDF) . Издательство Амстердамского университета. ISBN 978-90-5356-576-6.