Warum werden reguläre Ausdrücke mit Vereinigungs-, Verkettungs- und Sternoperationen definiert?

Ein regulärer Ausdruck wird rekursiv definiert als

1. für einige ein & egr ; & Sgr; ist ein regulärer Ausdruck,$a$$a \in \Sigma$
2. ist ein regulärer Ausdruck,$\varepsilon$
3. ist ein regulärer Ausdruck,$\emptyset$
4. wobei R 1 und R 2 reguläre Ausdrücke sind, ist ein regulärer Ausdruck,$(R_1 \cup R_2)$$R_1$$R_2$
5. wobei R 1 und R 2 reguläre Ausdrücke sind, ist ein regulärer Ausdruck,$(R_1 \circ R_2)$$R_1$$R_2$
6. wobei R 1 ein regulärer Ausdruck ist, ist ein regulärer Ausdruck.$(R_1)^*$$R_1$

Diese Definition stammt aus Seite 64 von

Sipser, Michael. Einführung in die Theorie der Berechnung, 3. Auflage. Cengage Learning, 2012.

Jetzt habe ich folgende Fragen.

• Warum enthält die Definition nicht das intersection, complementoderreverse Operationen?
• Wenn wir den 4. Punkt in R 1 ∩ R 2 ändern$R_1 \cap R_2$ , erhalten wir eine äquivalente Definition, dh für jede reguläre Sprache gibt es einen modifizierten regulären Ausdruck und umgekehrt?
• Ich weiß, dass diese Definition vollständig und genau definiert ist, aber warum wird sie anderen äquivalenten, genau definierten und vollständigen Definitionen vorgezogen?

1) Wenn wir auch Schnittmenge und Komplement zulassen, werden die resultierenden Ausdrücke manchmal als erweiterte reguläre Ausdrücke bezeichnet;; Da die regulären Sprachen unter booleschen Operationen geschlossen sind, wird durch sie nichts gewonnen. Es ist nur syntaktischer Zucker. Eine ähnliche Schlussfolgerung gilt für die umgekehrte Operation. Ein Grund dafür, dass in erster Linie alle anderen Operationen nicht erwähnt werden, ist das Ziel, die Definition so einfach wie möglich zu halten, damit (induktive) Beweise nicht in vielen Fällen erledigt werden müssen. Eine andere Ursache könnte sein, dass, wenn wir bestimmte Operationen zulassen, andere jedoch nicht, in einigen Fällen sehr unterschiedliche (unregelmäßige) Sprachklassen resultieren, z. B. wenn wir einen erweiterten regulären Ausdruck ohne den Sternoperator betrachten, wir eine richtige Unterklasse der regulären erhalten , die sogenannten sternfreien oder aperiodischen Sprachen, siehe Wikipedia: sternfreie Sprache .

2) Wenn wir die Punkte 1. - 6. beibehalten, aber Punkt 4. ändern, indem wir anstelle der Vereinigung die Schnittmenge verwenden, erhalten wir eine richtige Unterklasse der regulären Sprachen. Zum Beispiel könnten wir die Sprache nicht mehr beschreiben , da dies die Vereinigung von { a } und { b } beinhalten würde (siehe Beweis unten). Wenn wir eine Ergänzung zulassen, ändern sich die Dinge, da wir durch die Gesetze von DeMorgan wieder eine Vereinigung haben.$L = \{a,b\}$$\{a\}$$\{b\}$

3) Dies wurde teilweise von mir in 1) beantwortet, aber was meinst du, wenn du sagst, dass diese Definition bevorzugt wird? Ich kenne Definitionen, bei denen 2. weggelassen wird (wie wir bis 6. haben, dass ), oder 3. weggelassen wird (wie wir ∅ = L ( ¯ X ∗ ) haben), oder beide weggelassen werden ;; Dies ist also nicht die minimal mögliche Definition (sie gibt uns auch etwas syntaktischen Zucker, da wir zusätzliche Symbole haben, um { ε } und ∅ zu beschreiben ).$L(\emptyset^{\ast}) = \{\varepsilon\}$$\emptyset = L(\overline{ X^{\ast} }$$\{\varepsilon\}$$\emptyset$

EDIT : Mein erster erwähnten Kommentar in 2) falsch waren, Sprachen in der induktiven Schließung unter , * und ∩ nicht neccessarily sind Teilmengen von x * für einig x ∈ X , zum Beispiel betrachten L ( a ∘ b ) = { ein b } . Trotzdem haben wir, dass L = { a , b } durch einen solchen Ausdruck nicht beschrieben werden kann. Ich werde einen Beweis geben, nämlich ich beweise, dass wenn L = L ( R $\circ$$^{\ast}$$\cap$$x^{\ast}$$x \in X$$L(a\circ b) = \{ab\}$$L = \{a,b\}$$L = L(R)$für einigen Ausdruck mit dem vierten Elemente geändert, dann , wenn (und somit einem ≠ b ) { a , b } ⊆ L ⇒ a b ∈ L . Der Beweis , geht durch Induktion der Expression R . Für den Basisfall gilt es vakuum, nun sei angenommen, es gilt für L ( R 1 ) , L ( R 2 ) . Wenn 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)$ und { a , b } ⊆ L , dann { a , b } ⊆ L ( R i ) , i = 1 , 2, daher haben wir nach Induktionshypothese a b ∈ L ( R 1 ) ∩ L ( R 2 ) . Wenn$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)$ dannmüssen wirals a = a ⋅ ε = ε ⋅ a a ∈ L ( R 1 ) und ε ∈ L haben ( R 2 ) oder umgekehrt. Angenommen, der erste Fall. Wenn 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)$ , dann$b \in L(R_1)$$ab \in L(R_1)$$ab = ab\cdot \varepsilon \in L(R_1)L(R_2)$. Now suppose $b \in L(R_2)$, then we have $a\cdot b \in L(R_2)L(R_2)$ by definition of $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$. If $n = m = 1$ we find $ab \in L(R_1)$ by induction hypothesis, so suppose $n > 1$, but this gives $a \in L(R_1)$, similar either $m = 1$ or $m > 1$ gives $b \in L(R_1)$ and the induction hypothesis gives $ab \in L(R_1) \subseteq L(R_1^{\ast})$. $\square$

Remark: One commonly used conclusion: If $a = uw$, then $u = a$ or $w = a$. This follows as $1 = |a| = |uw| = |u| + |w|$, hence $|u| = 0$ and $|w| = 1$ or $|u| = 1$ and $|w| = 0$. In the first case we have $u = \varepsilon$ and hence $a = w$.

The technical report that introduced regular languages, regular expressions, and finite automata asks your question on page 70:

The question may occur to the reader, why did we select the particular three operations $E\vee F$, $EF$, and $E*F$?

(Soon afterwards, it was noted that $E^*$ is a more convenient operator than $E*F$ and equivalent in power. So these days, we use $E^*$ instead.)

The answer occupies several pages. First, it is remarked that the answer must be sought in whether the resulting languages form an interesting class and how they compare with languages described by other means. On page 72, it is remarked that negation and conjunction are redundant: they do not add any expressive power. On page 80 and further, it is proved that the regular languages are exactly the languages recognized by finite state machines.

In other words: Stefan's answer can safely be considered conclusive, as it was already given in the report that first introduced these concepts.

From this selection of operators (union, concatenation, and star) one can construct an NFA with a size linear to the size of the expression. On the other hand, if you add intersection and complementation, the size of the equivalent automaton may explode non-elementarily, which is usually not desirable.