Star free language vs regular language

Je me demandais, car $a^*$ lui - même est un langage sans étoile, est - il une langue régulière qui n'est pas un langage sans étoile? Pouvez-vous donner un exemple?

(de wikipdia ) Lawson définit les langues sans étoiles comme:

Une langue régulière est dite sans étoile si elle peut être décrite par une expression régulière construite à partir des lettres de l'alphabet, du symbole d'ensemble vide, de tous les opérateurs booléens - y compris la complémentation - et de la concaténation, mais pas d'étoile de Kleene.

Voici la preuve d' $a^*$ étoile:

$\emptyset$ est sans étoile$\Longrightarrow$
$\Sigma^*=\bar{\emptyset}$ est sans étoile$\Longrightarrow$
Si$A\subseteq\Sigma$ alors$\Sigma^*A\Sigma^*$ est sans étoile$\Longrightarrow$
Si$A\subseteq\Sigma$ alors$A^*=\overline{\Sigma^*(\Sigma \setminus A)\Sigma^*}$ est sans étoile

Dans la dernière ligne, nous avons $A^*=\overline{\Sigma^*(\Sigma \setminus A)\Sigma^*}$ , car tout mot qui n'est pas de forme $A^*$ contient une lettre dans $\Sigma \setminus A$ et vice versa.

Les langages réguliers sont ceux qui peuvent être décrits par une logique monadique faible du second ordre (WMSO) [1].

Les langages sans étoiles sont ceux qui peuvent être décrits par une logique$<$ de premier ordre avec < (FO [<]) [2].

Les deux logiques ne sont pas tout aussi puissantes. Un exemple pour un langage définissable par WMSO mais pas FO [<] - définissable est (qui est clairement régulier³); cela peut être montré en utilisant les jeux Ehrenfeucht-Fraissé ⁴.$(aa)^*$

1. Automates arithmétiques et finis de second ordre faibles de Büchi (1960)
2. Automates sans compteur de McNaughton et Papert (1971)

3. Une formule WMSO pour est$(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}$

   (Si le mot n'est pas vide, est l'ensemble de tous les indices pairs.)$X$

4. Voir aussi ici .

Schützenberger (1965) a donné une caractérisation algébrique des langues sans étoiles: une langue régulière est sans étoiles si et seulement si son monoïde syntaxique est apériodique. Contrairement à la caractérisation logique (sans étoile = FO [<]), cette caractérisation algébrique donne un algorithme pour décider si un langage régulier donné est sans étoile (le langage régulier peut être donné par un automate fini, une expression régulière ou un grammaire régulière). En utilisant la caractérisation logique (due à McNaughton et Papert), on peut alors décider du problème suivant: étant donné une formule WMSO, existe-t-il une formule FO décrivant le même langage?

M.-P. Schützenberger, On finite monoids having only trivial subgroups, Information and Control 8 (1965), 190-194.

R. ~ McNaughton et S. ~ Papert, Counter-free automata, The MIT Press, Cambridge, Mass.-Londres, 1971.

Une preuve complète du théorème de Schützenberger peut être trouvée dans divers manuels ou articles d'enquête. Pour une présentation élémentaire de l'algorithme correspondant (sans preuve), voir

J.-É. Pin, Semi-groupes finis et langues reconnaissables: une introduction, dans OTAN Advanced Study Institute Semigroups, Formal Languages ​​and Groups , J.Fountain (éd.), 1-32, Kluwer Academic Publisher, (1995).

Les langues sans étoiles sont décrites par des expressions régulières qui incluent la concaténation, la complémentation, l'union, l'intersection, mais pas d'étoile de Kleene.

Étant donné que les langues régulières sont fermées sous toutes ces opérations (où la complémentation est le point crucial), chaque langue sans étoile est également régulière.

Peut-être voulez-vous dire l'inverse? Toutes les langues régulières sont-elles sans étoiles? La réponse à ce dernier est non. Consultez ce document pour plus de détails.

Un exemple de séparation simple est (aa) *. Plus sophistiqué: toutes les chaînes binaires avec une parité paire (ou impaire).