Мне было интересно, так как * сама звезда-свободный язык, есть регулярный язык , который не является звездой свободного языка? Не могли бы вы привести пример?
(из википедии ) Лоусон определяет беззвездные языки как:
Обычный язык называется свободным от звезд, если он может быть описан с помощью регулярного выражения, составленного из букв алфавита, символа пустого множества, всех логических операторов - включая дополнение - и конкатенации, но без звезды Клини.
Вот доказательство того, имеет звезд:
является звездой свободной
является звезда свободной
Если ⊆ Е , то Е * Е * является звезда свободной ⟹ Если ⊆ Е , то * = ¯ Е * ( Е ∖ ) Е * является звезды бесплатно
В последней строке мы имеем , потому что любое словокоторое не имеет видасодержит букву ви наоборот.
источник
Ответы:
Обычные языки - это те, которые могут быть описаны слабой монадической логикой второго порядка (WMSO) [1].
Беззвездные языки - это те, которые можно описать логикой первого порядка с помощью< (FO [<]) [2].
Две логики не одинаково сильны. Одним из примеров языка, определяемого WMSO, но не определяемого FO [<], является (который, безусловно, является регулярным3); это можно показать с помощью игр Ehrenfeucht-Fraissé ⁴.( )*
WMSO-формула для имеет вид( )*
источник
Шютценбергер (1965) дал алгебраическую характеристику беззвездных языков: регулярный язык свободен от звезд тогда и только тогда, когда его синтаксический моноид апериодичен. В отличие от логической характеристики (без звездочек = FO [<]) эта алгебраическая характеристика дает алгоритм , чтобы решить данный регулярный язык , является ли звездой свободной (регулярный язык может быть задан конечным автоматом, регулярным выражением или обычная грамматика). Используя логическую характеристику (благодаря МакНотону и Паперту), можно решить следующую проблему: с учетом формулы WMSO существует ли формула FO, описывающая тот же язык?
M.-P. Шютценбергер, О конечных моноидах, имеющих только тривиальные подгруппы, Информация и управление 8 (1965), 190-194.
Р. ~ McNaughton и С. ~ Паперт, счетчик свободных автоматов, The MIT Press, Cambridge, штат Массачусетс Лондон, 1971.
Полное доказательство теоремы Шютценбергера можно найти в различных учебниках или обзорных статьях. Элементарное представление соответствующего алгоритма (без доказательства) см.
J.-É. Пин, Конечные полугруппы и узнаваемые языки: введение, Полугруппы Института передовых исследований НАТО, Формальные языки и группы , J. Fountain (ред.), 1-32, Kluwer Academic Publishing, (1995).
источник
Звездные свободные языки описываются регулярными выражениями, которые включают конкатенацию, дополнение, объединение, пересечение, но без клини-звезды.
Поскольку обычные языки закрыты для всех этих операций (где комплементация является критической точкой), то каждый язык без звезд также является регулярным.
Возможно, вы имеете в виду обратное? Все ли обычные языки без звезд? Ответ на последний - нет. Смотрите эту статью для деталей.
источник
Простой разделительный пример: (аа) *. Более сложный: все двоичные строки с четной (или нечетной) четностью.
источник