Pourquoi les expressions régulières sont-elles définies avec l'union, la concaténation et les opérations en étoile?

Une expression régulière est définie récursivement comme

1. $a$ pour certains, est une expression régulière,$a \in \Sigma$
2. $\varepsilon$ est une expression régulière,
3. $\emptyset$ est une expression régulière,
4. $(R_1 \cup R_2)$ où et sont des expressions régulières est une expression régulière,$R_1$$R_2$
5. $(R_1 \circ R_2)$ où et sont des expressions régulières est une expression régulière,$R_1$$R_2$
6. $(R_1)^*$ où est une expression régulière est une expression régulière.$R_1$

Cette définition est tirée de la page 64 de

Sipser, Michael. Introduction à la théorie du calcul, 3e édition. Cengage Learning, 2012.

Maintenant, j'ai les questions suivantes.

• Pourquoi ne pas la définition contient les intersection, complementou les reverseopérations?
• Si nous changeons le 4ème élément en , -nous une définition équivalente, c'est-à-dire que pour chaque langue régulière, il y a une expression régulière modifiée et vice versa?$R_1 \cap R_2$
• Je sais que cette définition est complète et bien définie, mais pourquoi est-elle préférée à d'autres définitions équivalentes, bien définies et complètes?

1) Si nous autorisons également l'intersection et le complément, les expressions résultantes sont parfois appelées expressions régulières étendues; comme les langues régulières sont fermées sous des opérations booléennes, rien n'y est gagné. C'est juste du sucre syntaxique. Une conclusion similaire vaut pour l'opération inverse. Une partie de la raison pour laquelle en première instance toutes les autres opérations ne sont pas mentionnées est le but de garder la définition aussi simple que possible, de sorte que les preuves (inductives) n'aient pas à prendre en charge de nombreux cas. Une autre cause pourrait être que si nous autorisons certaines opérations, mais pas d'autres, dans certains cas, des classes de langage très distinctes (sous-régulières), par exemple si nous considérons l'expression régulière étendue sans l'opérateur étoile, alors nous obtenons une sous-classe appropriée des classes régulières , les langues dites sans étoiles ou apériodiques, voir wikipedia: langage sans étoiles .

2) Si nous conservons les éléments 1. - 6. mais modifions simplement l'élément 4. en utilisant l'intersection au lieu de l'union, nous obtenons une sous-classe appropriée des langues régulières. Par exemple, nous ne pourrions plus décrire le langage car il impliquerait l'union de { a } et { b } (voir la preuve ci-dessous). Si nous permettons la complémentation, les choses changent car nous avons l'union de retour par les lois de DeMorgan.$L = \{a,b\}$$\{a\}$$\{b\}$

3) J'ai répondu en partie en 1), mais que voulez-vous dire lorsque vous dites que cette définition est préférée? Je connais les définitions où 2. est omis (comme nous l'avons par 6. que ), ou 3. est omis (comme nous avons ∅ = L ( ¯ X ∗ )), ou les deux sont omis ; donc celle-ci n'est pas la définition minimale possible (elle nous donne aussi du sucre syntaxique car nous avons des symboles supplémentaires pour décrire { ε } et ∅ ).$L(\emptyset^{\ast}) = \{\varepsilon\}$$\emptyset = L(\overline{ X^{\ast} }$$\{\varepsilon\}$$\emptyset$

EDIT : Mon premier commentaire mentionné en 2) était faux, les langues dans la fermeture inductive sous , ∗ et ∩ ne sont pas nécessairement des sous-ensembles de x ∗ pour certains x ∈ X , par exemple, considérons L ( a ∘ b ) = { a b } . Néanmoins nous avons que L = { a , b } ne pourrait pas être décrit par une telle expression. Je vais donner une preuve, à savoir je prouve que si L = L ( R $\circ$$^{\ast}$$\cap$$x^{\ast}$$x \in X$$L(a\circ b) = \{ab\}$$L = \{a,b\}$$L = L(R)$pour une expression avec l'élément 4 modifié, alors si (et donc un ≠ b ) { a , b } ⊆ L ⇒ un b ∈ L . La preuve passe par induction sur l'expression R . Pour le cas de base, il est vide, supposons maintenant qu'il vaut pour L ( R 1 ) , L ( R 2 ) . Si L = L ( R 1$X = \{a,b\}$$a\ne b$

$$\{a,b\} \subseteq L \Rightarrow ab \in L.$$ $R$$L(R_1), L(R_2)$ et { a , b } ⊆ L , puis { a , b } ⊆ L ( R i ) , i = 1 , 2 donc par hypothèse d'induction on a a b ∈ L ( R 1 ) ∩ L ( R 2 ) . Si$L = L(R_1 \cap R_2) = L(R_1) \cap L(R_2)$$\{a,b\} \subseteq L$$\{a,b\} \subseteq L(R_i), i = 1,2$$ab \in L(R_1) \cap L(R_2)$ alors comme a = a ⋅ ε = ε ⋅ a nous devons avoir a ∈ L ( R 1 ) et ε ∈ L ( R 2 ) ou vice versa. Supposons le premier cas. Si b ∈ L $\{a,b\} \subseteq L(R_1\circ R_2) = L(R_1)L(R_2)$$a = a\cdot \varepsilon = \varepsilon\cdot a$$a\in L(R_1)$$\varepsilon \in L(R_2)$ , puis a b ∈ L ( R 1 ) par hypothèse d'induction, d'où a b = a b ⋅ ε ∈ L ( R 1 ) L ( R 2 ) . Supposons maintenant b ∈ L ( R 2 ) , alors nous avons un ⋅ b ∈ L ( R 2 ) L ( R 2 ) par définition de$b \in L(R_1)$$ab \in L(R_1)$$ab = ab\cdot \varepsilon \in L(R_1)L(R_2)$$b \in L(R_2)$$a\cdot b \in L(R_2)L(R_2)$ . Enfin si a , b ∈ L ( R ∗ 1 ) , alors a ∈ L ( R 1 ) n et b ∈ L ( R 2 ) m pour certains n , m > 0 . Si n = m = 1 on trouve a b ∈ L ( $L(R_1)L(R_2)$$a,b \in L(R_1^{\ast})$$a \in L(R_1)^n$$b \in L(R_2)^m$$n,m > 0$$n = m = 1$ par hypothèse d'induction, supposons donc n > 1 , mais cela donne a ∈ L ( R 1 ) , similaire soit m = 1 ou m > 1 donne b ∈ L ( R 1 ) et l'hypothèse d'induction donne a b ∈ L ( R 1 ) ⊆ L ( R ∗ 1 ) . $ab \in L(R_1)$$n > 1$$a \in L(R_1)$$m = 1$$m > 1$$b \in L(R_1)$$ab \in L(R_1) \subseteq L(R_1^{\ast})$$\square$

Remarque: Une conclusion couramment utilisée: si , alors u = a ou w = a . Cela suit comme 1 = | a | = | u w | = | u | + | w | , donc | u | = 0 et | w | = 1 ou | u | = 1 et | w | $a = uw$$u = a$$w = a$$1 = |a| = |uw| = |u| + |w|$$|u| = 0$$|w| = 1$$|u| = 1$ . Dans le premier cas, nous avons u = ε et donc a = w .$|w| = 0$$u = \varepsilon$$a = w$

Le rapport technique qui a introduit les langages réguliers, les expressions régulières et les automates finis pose votre question à la page 70:

La question peut se poser au lecteur, pourquoi avons-nous choisi les trois opérations particulières $E\vee F$ , $EF$ et $E*F$ ?

(Peu de temps après, il a été noté que $E^*$ est un opérateur plus pratique que $E*F$ et équivalent en puissance. Donc, de nos jours, nous utilisons plutôt $E^*$ .)

La réponse occupe plusieurs pages. Tout d'abord, il est à noter que la réponse doit être recherchée pour savoir si les langues résultantes forment une classe intéressante et comment elles se comparent aux langues décrites par d'autres moyens. À la page 72, on remarque que la négation et la conjonction sont redondantes: elles n'ajoutent aucun pouvoir expressif. À la page 80 et plus loin, il est prouvé que les langages réguliers sont exactement les langages reconnus par les machines à états finis.

En d'autres termes: la réponse de Stefan peut sans risque être considérée comme concluante, car elle a déjà été donnée dans le rapport qui a introduit pour la première fois ces concepts.

A partir de cette sélection d'opérateurs (union, concaténation et étoile), on peut construire un NFA avec une taille linéaire à la taille de l'expression. D'un autre côté, si vous ajoutez l'intersection et la complémentation, la taille de l'automate équivalent peut exploser de manière non élémentaire, ce qui n'est généralement pas souhaitable.