Zwischenbetrachtung / Resümee:
Wir kennen bereits den Mechanismus des Erkennens (durch [interner Verweis =>]Automaten) einer Sprache (erzeugt über einem endlichen Alphabet). Diese Sprachen, losgelöst von den [interner Verweis =>]Akzeptoren, genauer zu betrachten und so den Mechanismus des Erzeugen (durch [interner Verweis =>]Grammatiken oder reguläre Ausdrücke) kennenzulernen ist Aufgabe der folgenden Absätze.

Sprachen wurden von [interner Verweis =>]Noam Chomsky genauer untersucht. Von ihm stammt die Unterteilung der Klasse aller Sprachen in vier Kategorien:
Sprachen der Stufe:sind:und werden akzeptiert von:
0aufzählbare SprachenTuringmaschinen
1kontextsensitive Sprachenlinear beschränkten Automaten
2kontextfreie SprachenPush-Down-Automaten / Kellerautomaten
3reguläre Sprachendeterministischen Automaten
[interner Verweis =>]ausführlicher bitte!

Unser erstes Ziel ist es, die Sprachklasse zu klassifizieren, die wir durch [interner Verweis =>]endliche Akzeptoren erkennen. Es wird gezeigt werden, daß dies genau der Klasse der regulären Sprachen entspricht:

4.3. Reguläre Sprachen

Definition N: (Syntaxdefinition)
Sei X ein Alphabet und V={ ( , ) , * , È, ·, Æ } ein Vorrat an Zeichen.
Dann ist die Mengen der regulären Ausdrücke Reg(X) folgendermaßen definiert:
  1. "xÎX( xÎReg(X) ) Û XÍReg(X)
  2. ÆÎReg(X)
  3. "R,QÎReg(X)( (RÈQ)ÎReg(X) Ù (R·Q)ÎReg(X) )
  4. "RÎReg(X)( R*ÎReg(X) )
  5. Reg(X) ist kleinste Teilmenge von (XÈV)*, die i) bis iv) erfüllt

Beispiele:
Sei X={x1,x2,x3} Dann sind u.a. folgende Ausdrücke reguläre Ausdrücke:

Diese Folgen, bestehend aus Zeichen und Elementen aus XÈV sind bisher jedoch sinnleer! Sie entstehen durch bloßes Anwenden der Regeln i) bis iv). Die nun notwendige Interpretation folgt jetzt:

Definition O: (Semantikdefinition)
Die Bedeutung eines regulären Ausdruckes über X wird durch folgende Abbildung s:Reg(X)®2X* festgelegt, die wie folgt induktiv definiert ist:
  1. xÎX Þ s(x)={x}
  2. s(Æ)=Æ
  3. "R,QÎReg(X)( s(RÈQ)=s(R)Èd(Q) Ù s(R·Q)=s(R)·d(Q) )
  4. "RÎReg(X)( s(R*)=s(R)* )
Reg(x) ist genaugenommen nur eine Menge von Zeichenreihen, den regulären Ausdrücken. Diesen Ausdrücken gibt s eine Bedeutung, die Interpretation. Diese Bedeutung ist einen Sprache. s(x) ist die Sprache, die der reguläre Ausdruck x beschreibt.
Ist s(r) = s(r'), so heißen r und r' äquivalent.

Beispiele:

Bemerkung:
ergänzend zu den Semantikregeln gibt es Prioritätsregeln, die eine Änderung der Syntax mit sich bringen, jedoch die Bedeutung des Ausdruckes unverändert lassen:
  1. "·" wird vor "È" interpretiert
  2. Weglassen äußerer Klammern
  3. Weglassen des Zeichens "·"

Beispiel:

Definition P:
Sei X ein Alphabet.
Eine Sprache LÍX* heißt reguläre Sprache, wenn es einen regulären Ausdruck RÎReg(X) mit s(R)=L gibt.
(LÍX* heißt reguläre Sprache :Û $RÎReg(X)( s(R)=L ).
Die Menge aller regulären Sprachen über X bezeichnen wir mit R(X).
Die Klasse aller regulären Sprachen bezeichnen wir mit R.

Äquivalenzproblem für reguläre Ausdrücke:
Sei R ein regulärer Ausdruck mit: R = a(a*Èb*)* È (bÈc)(aÈbÈc)* È (ca)* ,
dann folgt für s(R): s(R) = { wÎX* |   wÎ{a,b}* und w beginnt mit einem a
    oder wÎ{a,b,c}* und w beginnt nicht mit a
    oder w=e
}      
Der dritte Fall (ca)* kann auf w=e "runtergewertet" werden; Dies ergibt sich aus: (ca)*\{e} Í (bÈc)(aÈbÈc)*, somit muß nur noch der Fall {e} hinzugefügt werden.
Sei R‘ ein regulärer Ausdruck mit: R‘ = a(aÈb)* È (bÈc)(aÈbÈc)* È Æ*
Ersichtlich ist: s(R) = s(R‘)

Aus dieser Betrachtung ergibt sich folgende
Frage: Gibt es einen Algorithmus, der für jedes beliebige Alphabet X und für je zwei reguläre Ausdrücke R,R’ÎReg(X) entscheidet, ob s(R) = s(R‘)?
Antwort: Ja, dieses Problem ist algorithmisch lösbar, aber sehr aufwendig (NP-hart [nichtdeterministisch in polynomiel viel Zeit lösbar]).

Satz Q: (Gleichheit von R und DA)
Die Klasse aller regulären Sprachen und die Klasse aller, durch endliche [interner Verweis =>]Automaten akzeptierbarer Sprachen ist gleich. (R=DA)

Beweis von Satz Q:
Zeige zuerst die mengentheoretische Inklusion von R in DA ("Í"):
Definition N Þ R ist kleinste Klasse von Sprachen, die
         die leere Menge enthält,
         die alle Mengen {x} (mit xÎX) enthält,
         die gegen Vereinigung, Konkatenation und *-Bildung abgeschlossen ist;
Lemma E Þ DA enthält die leere Menge, DA enthält alle endlichen Mengen;
Satz D, Satz K Þ DA ist abgeschlossen gegen *-Bildung, Konkatenation und Vereinigung;
Þ RÍDA

Zeige nun die mengentheoretische Inklusion von DA in R ("Ê"):
Beweisidee: Wähle einen beliebigen [interner Verweis =>]endlichen deterministischen Akzeptor (der L(A) erkennt) und konstruiere dazu einen regulären Ausdruck R (mit der Bedeutung s(R)), so daß L(A)=s(R).
Sei A=(X,S, d,1,F) ein [interner Verweis =>]endlicher deterministischer Akzeptor mit n Zuständen (o.B.d.A.: S={1,...,n}).
Beweismethode: Vollständige Induktion über die (Nummern der) Zwischenzustände, die man benötigt, um von einem Zustand i in einen Zustand j zu gelangen. Definiere für alle i,jÎS und kÎ{0,1,...,n} ( entspricht: kÎ({0}ÈS) ) :
Wijk := { wÎX | d(i,w)=j Ù "u,vÎX*\{e}( w=uv Þ d(i,u)£k ) }
(Wijk sei die Menge aller Wörter mit denen man vom Zustand i in den Zustand j kommt und unterwegs nur über die Zwischenzustände von 1 bis k kommt)

Induktionsanfang: (k=0)
Wij0 Í XÈ{e} ( von i nach j ohne Zwischenzustände Þ |w|=1 oder w=e )
Wij0 kann also durch einen regulären Ausdruck dargestellt werden, nämlich: {X
Æ*


Induktionsannahme: (k ist eine beliebige natürliche Zahl)
Wir nehmen an, für ein beliebiges k³0 und für alle i,jÎS seien die Mengen Wijk bereits konstruiert und durch einen regulären Ausdruck darstellbar. Dann gilt für alle i,jÎS:

Induktionsschritt: (zeige "i,jÎ{1,...,n}"kÎ{0,1,...,n}(WijkÎR Þ Wijk+1ÎR) )
Es zeigt sich: Wijk+1 = Wijk È Wi(k+1)k·(W(k+1)(k+1)k)*·W(k+1)jk
Die Menge der Wege von i nach j über die Zwischenzustände 1 bis (k+1) (Wijk+1) setzt sich zusammen aus (trivialerweise) allen Wegen von i nach j über die ersten (k) Zustände (Wijk) UND den Wegen, die tatsächlich den Zustand (k+1) passieren.
Diese Wege kann man als Wegfolgen (Konkatenation einzelner Wegstücke) betrachten, wobei man für den Anfang jeder Wegfolge der Zustand i, für das Ende der Zustand j angenommen wird (es geht ja von i nach j). Zwischendurch jedoch wähle man die Wegstücke so, so daß sie mit dem Zustand (k+1) enden und beginnen. Also vom Zustand i in den Zustand (k+1) gehen (erstes Wegstück), diesen Zustand (k+1) eventuell immer wieder durchlaufen (weitere Wegstücke) und anschließend in den Zustand j gehen (letztes Wegstück) (Wi(k+1)k·(W(k+1)(k+1)k)*·W(k+1)jk).
Die einzelnen Wegstücke haben nur Zwischenstops in Zuständen von 1 bis k.
Und diese Teilstücke (Wijk , Wi(k+1)k , (W(k+1)(k+1)k)* und W(k+1)jk) sind bereits (nach Induktionsannahme) als regulärer Ausdruck dargestellt. Da auch die Vereinigung, die *-Bildung und die Konkatenation wiederum reguläre Ausdrücke ergeben, ist auch die Folge (Wijk È Wi(k+1)k·(W(k+1)(k+1)k)*·W(k+1)jk) wiederum ein regulärer Ausdruck.

Fazit: Ist Wijk als regulärer Ausdruck darstellbar, dann ist es auch Wijk+1!
Da wir den Anfang mit k=0 gezeigt haben, gilt dies folglich für alle beliebigen natürlichen Zahlen.

Die akzeptierte Sprache des [interner Verweis =>]Akzeptors L(A) ist folglich die Vereinigung aller Wege vom Startzustand in alle möglichen Endzustände (wobei als Zwischenzustände alle Zustände des [interner Verweis =>]Akzeptors möglich sind):
L(A) = È W1jn    ; dies ist ebenfalls ein regulärer Ausdruck
 jÎF
Þ L(A)ÎR, für einen beliebigen [interner Verweis =>]endlichen deterministischen Akzeptor A
Þ DAÍR

Dieser Beweis hat einen schönen Nebeneffekt. Er gibt eine Anleitung, um für jeden [interner Verweis =>]Akzeptor die erkannte Sprache zu ermitteln, indem wir den zugehörigen regulären Ausdruck bestimmen.

In folgendem kleinen Programm ist die Anleitung realisiert: [interner Verweis =>]Programm

Beispiel:
Gegeben sei der [interner Verweis =>]Akzeptor A = ({a,b},{1,2},d,1,{2}) mit folgendem (graphisch dargestellten) d:

dann ist ersichtlich (Betrachtung 1):
W110 = {e}W120 = {a,b}
W210 = {a}W220 = {e,b}
daraus folgt (Betrachtung 2):
W111 = W110 È W110·(W110)*·W110={e}
W121 = W120 È W110·(W110)*·W120= {a,b}
W211 = W210 È W210·(W110)*·W120= {a}
W221 = W220 È W210·(W110)*·W120= {e,b}È{aa,ab}
daraus folgt (Betrachtung 3):
W112 = W111 È W121·(W221)*·W211= {e}È{a,b}{e,b,aa,ab}*{a}
         = {e}È{a,b}{b,aa,ab}*{a}
W122 = W121 È W121·(W221)*·W221= {a,b}È{a,b}{e,b,aa,ab}*{e,b,aa,ab}
         = {a,b}È{a,b}{e,b,aa,ab}*
         = {a,b}È{b,aa,ab}*
W212 = W211 È W221·(W221)*·W211
         = {a}È{e,b,aa,ab}{e,b,aa,ab}*{a} = {a}È{b,aa,ab}*
W222 = W221 È W221·(W221)*·W221
         = {e,b,aa,ab}È{e,b,aa,ab}{e,b,aa,ab}*{e,b,aa,ab}
         = {b,aa,ab}*
nun ergibt sich für die Betrachtung von L(A):
L(A) = È W1j2 = W122 = {a,b}È{b,aa,ab}*
 jÎF
ein entsprechender regulärer Ausdruck R ist demnach:
R = (aÈb)·((bÈ(a·a))È(a·b))* = (aÈb)((bÈaa)Èab)*