Język bez gwiazdek a język zwykły

Zastanawiałem się, ponieważ * jest sam język gwiazda wolna, czy istnieje język regularny, który nie jest językiem gwiazdy darmo? Czy możesz podać przykład?$a^*$

(z wikipdii ) Lawson definiuje języki bez gwiazdek jako:

Mówi się, że w zwykłym języku nie ma gwiazd, jeśli można go opisać wyrażeniem regularnym zbudowanym z liter alfabetu, pustego zestawu znaków, wszystkich operatorów boolowskich - w tym uzupełnienia - i konkatenacji, ale bez gwiazdy Kleene.

Oto dowód, $a^*$ ma gwiazd:

$\emptyset$ zawiera gwiazd$\Longrightarrow$
$\Sigma^*=\bar{\emptyset}$ zawiera gwiazd$\Longrightarrow$
Jeśli$A\subseteq\Sigma$ to$\Sigma^*A\Sigma^*$ zawiera gwiazd$\Longrightarrow$
Jeśli$A\subseteq\Sigma$ to$A^*=\overline{\Sigma^*(\Sigma \setminus A)\Sigma^*}$ wynosi bez gwiazdek

W ostatnim wierszu mamy $A^*=\overline{\Sigma^*(\Sigma \setminus A)\Sigma^*}$ , ponieważ każde słowo, które nie ma formy $A^*$ zawiera literę w $\Sigma \setminus A$ i odwrotnie.

Zwykłe języki to te, które można opisać słabą monadyczną logiką drugiego rzędu (WMSO) [1].

Języki bez gwiazdek to te, które można opisać za pomocą logiki pierwszego rzędu za pomocą $<$ (FO [<]) [2].

Te dwie logiki nie są jednakowo potężne. Przykładem dla języka, który jest WMSO definiowane ale FO [<] - definiowane jest (co jest wyraźnie regular³); można to pokazać za pomocą gier Ehrenfeucht-Fraissé ⁴.$(aa)^*$

1. Słaba arytmetyka i automaty skończone drugiego rzędu autorstwa Büchi (1960)
2. Bezproblemowe automaty McNaughton i Papert (1971)

3. WMSO-formuła jest$(aa)^*$

   $\ \begin{align} \bigl[ \forall x. P_a(x)\bigr] \land \Bigl[ \exists x. P_a(x) \to \bigl[ \exists X. X(0) &\land [\forall x,y. X(x) \land \operatorname{suc}(x,y) \to \lnot X(y)] \\ &\land [\forall x,y. \lnot X(x) \land \operatorname{suc}(x,y) \to X(y)] \\ &\land [\forall x. \operatorname{last}(x) \to \lnot X(x)] \bigr] \Bigr] \;. \end{align}$

   (Jeśli słowo nie jest puste, jest zbiorem wszystkich parzystych wskaźników).$X$

4. Zobacz także tutaj .

Schützenberger (1965) podał algebraiczną charakterystykę języków bez gwiazd: w zwykłym języku nie ma gwiazd, tylko wtedy, gdy jego składniowa monoida jest aperiodyczna. W przeciwieństwie do charakterystyki logicznej (bez gwiazd = FO [<]), ta charakterystyka algebraiczna daje algorytm do decydowania, czy dany język regularny jest bez gwiazd (język regularny może być nadany przez automat skończony, wyrażenie regularne lub gramatyka regularna). Korzystając z logicznej charakterystyki (ze względu na McNaughton i Papert), można następnie zdecydować o następującym problemie: biorąc pod uwagę formułę WMSO, czy istnieje formuła FO opisująca ten sam język?

POSEŁ. Schützenberger, O skończonych monoidach posiadających tylko trywialne podgrupy, Informacja i kontrola 8 (1965), 190–194.

R. ~ McNaughton i S. ~ Papert, Automaty bezlicznikowe, The MIT Press, Cambridge, Mass.-London, 1971.

Pełny dowód twierdzenia Schützenbergera można znaleźć w różnych podręcznikach lub artykułach przeglądowych. Aby zapoznać się z podstawową prezentacją odpowiedniego algorytmu (bez dowodu), patrz

J.-É. Przypinka, skończone półgrupy i rozpoznawalne języki: wprowadzenie, w półgrupach NATO Advanced Study Institute, Formal Languages ​​and Groups , J. Fountain (éd.), 1-32, wydawcy akademiccy Kluwer, (1995).

Języki wolne od gwiazd są opisane wyrażeniami regularnymi, które obejmują konkatenację, uzupełnienie, zjednoczenie, przecięcie, ale bez gwiazdy Kleene.

Ponieważ zwykłe języki są zamknięte dla wszystkich tych operacji (gdzie uzupełnienie jest kluczowym punktem), każdy język bez gwiazdek jest również regularny.

Może masz na myśli rozmowę? Czy wszystkie zwykłe języki są wolne od gwiazdek? Odpowiedź na to drugie pytanie brzmi: nie. Zobacz ten artykuł, aby uzyskać szczegółowe informacje.

Prostym przykładem oddzielającym jest (aa) *. Bardziej wyrafinowane: wszystkie ciągi binarne z parzystą (lub nieparzystą) parzystością.