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

11

Ein regulärer Ausdruck wird rekursiv definiert als

  1. für einige ein & egr ; & Sgr; ist ein regulärer Ausdruck,aaΣ
  2. ist ein regulärer Ausdruck,ε
  3. ist ein regulärer Ausdruck,
  4. wobei R 1 und R 2 reguläre Ausdrücke sind, ist ein regulärer Ausdruck,(R1R2)R1R2
  5. wobei R 1 und R 2 reguläre Ausdrücke sind, ist ein regulärer Ausdruck,(R1R2)R1R2
  6. wobei R 1 ein regulärer Ausdruck ist, ist ein regulärer Ausdruck.(R1)R1

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 1R 2 ändernR1R2 , 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?
Ali Shakiba
quelle
2
Bitte beschränken Sie sich auf eine Frage pro Beitrag.
Raphael

Antworten:

16

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()={ε}=L(X¯{ε}

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 )xxXL(ab)={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 R.X={a,b}ab

{a,b}LabL.
RL(R1),L(R2) 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 ) . WennL=L(R1R2)=L(R1)L(R2){a,b}L{a,b}L(Ri),i=1,2abL(R1)L(R2) 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}L(R1R2)=L(R1)L(R2)a=aε=εaaL(R1)εL(R2) , dannbL(R1)abL(R1)ab=abεL(R1)L(R2). Now suppose bL(R2), then we have abL(R2)L(R2) by definition of L(R1)L(R2)a,bL(R1)aL(R1)nbL(R2)mn,m>0. If n=m=1 we find abL(R1) by induction hypothesis, so suppose n>1, but this gives aL(R1), similar either m=1 or m>1 gives bL(R1) and the induction hypothesis gives abL(R1)L(R1).

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=ε and hence a=w.

StefanH
quelle
2
Indeed {a,b} is not in the set of "subregular" languages, but {a,b} is because {a,b}=(ab).
rici
Yes, sometimes it is a little bit tricky to see what could be expressed and what not as with a clever combination of star and others you can get quite far.
StefanH
10

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 EF, EF, and EF?

(Soon afterwards, it was noted that E is a more convenient operator than EF 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.

reinierpost
quelle
Thanks for the link. I always explain to my students that the operations are natural abstractions from choice (like if-then-else) sequence (instructions following one another) and iteration (like while-do). But apparently that is not mentioned by Kleene?
Hendrik Jan
I'm just a guy who looked up Kleene's article and was surprised that everything in my answer was already in there. I don't know anything else. So I suppose the answer is to read the article and perhaps look for anything that Kleene wrote on this before.
reinierpost
4

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.

doganulus
quelle