Звезда свободного языка против обычного языка

11

Мне было интересно, так как * сама звезда-свободный язык, есть регулярный язык , который не является звездой свободного языка? Не могли бы вы привести пример?a


(из википедии ) Лоусон определяет беззвездные языки как:

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


Вот доказательство того, a имеет звезд:

является звездой свободной
Σ=¯ является звезда свободной
ЕслиЕ , то Е * Е * является звезда свободной ЕслиЕ , то * = ¯ Е * ( Е ) Е * является звезды бесплатноAΣΣ*AΣ*
AΣA*знак равноΣ*(ΣA)Σ*¯

В последней строке мы имеем A*знак равноΣ*(ΣA)Σ*¯ , потому что любое словокоторое не имеет видаA*содержит букву вΣAи наоборот.

Без названия
источник
A*Σ*AΣ*
повторная
@reinierpost Вы неправильно читаете уравнение. В верхней части и в верхней части всего уравнения есть два столбца дополнения . Извините, я думаю, что я не был хорош в форматировании в 2013 году.A
Без названия
@reinierpost Я отредактировал пост, чтобы его было легче читать. Спасибо за ответ.
Без названия
Спасибо! Трудно пропустить сейчас.
reinierpost

Ответы:

11

Обычные языки - это те, которые могут быть описаны слабой монадической логикой второго порядка (WMSO) [1].

Беззвездные языки - это те, которые можно описать логикой первого порядка с помощью < (FO [<]) [2].

Две логики не одинаково сильны. Одним из примеров языка, определяемого WMSO, но не определяемого FO [<], является (который, безусловно, является регулярным3); это можно показать с помощью игр Ehrenfeucht-Fraissé ⁴.(aa)*


  1. Слабые арифметические и конечные автоматы второго порядка Бьючи (1960)
  2. Безналичные автоматы МакНотона и Пейперта (1971)
  3. WMSO-формула для имеет вид(aa)*

     [Икс,пa(Икс)][Икс,пa(Икс)[Икс,Икс(0)[Икс,Y,Икс(Икс)SUC(Икс,Y)¬Икс(Y)][Икс,Y,¬Икс(Икс)SUC(Икс,Y)Икс(Y)][Икс,прошлой(Икс)¬Икс(Икс)]]],

    Икс

  4. Смотрите также здесь .
Рафаэль
источник
Я знаю, что такое «монадное» в логике. Как вы не знаете , что такое «слабое» ограничение?
Хендрик Ян
1
ω
14

Шютценбергер (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).

J.-E. Штырь
источник
7

Звездные свободные языки описываются регулярными выражениями, которые включают конкатенацию, дополнение, объединение, пересечение, но без клини-звезды.

Поскольку обычные языки закрыты для всех этих операций (где комплементация является критической точкой), то каждый язык без звезд также является регулярным.

Возможно, вы имеете в виду обратное? Все ли обычные языки без звезд? Ответ на последний - нет. Смотрите эту статью для деталей.

Shaull
источник
да я имел ввиду обратное, отредактировал вопрос.
Без названия
1

Простой разделительный пример: (аа) *. Более сложный: все двоичные строки с четной (или нечетной) четностью.

Хольгер Петерсен
источник
1
Что это добавляет к принятому ответу?
Рафаэль
@Raphael Пример четности. Хотя было бы неплохо, если бы Хольгер объяснил, почему это не без звезд.
Дэвид Ричерби