cards-deck: university::theo_complexity

Reguläre Ausdrucke - Regular Expressions :

part of [[112.00_anchor_overview]] requires 112.01_Sprachen

historische Einschätzung:

Reguläre Ausdrücke wurden von Stephen Cole Kleene (1909 - 1994) begründet und für diese auch ein Beweis geliefert: Lemma 1 Sprache durch regex –> ist regulär und [Lemma 2 Sprache ist regulär –> $existsR$ die die Sprache beschreibt.](#Lemma%202%20Sprache%20ist%20regulär%20–>%20%20die%20die%20Sprache%20beschreibt.) Resource: Representation of Events in Nerve Nets and Finite Automata (USAF RAND project Research Memorandum RM-704, 15.12. 1951)

Intuition zu Regulären Ausdrücken:

Reguläre Ausdrücke kommen in vielen Variationen, Umgebungen statt - beispielsweise Bash / Unix - und können mehrere Aussagen in kleinen Ausdrücken beschrieben. Das heißt, sie können viele Möglichkeiten durch Angabe von Verallgemeinerten Definitionen beschreiben. Beispielsweise:

grep -r '[Vv]orlesung * 20[0-2][0-9]'

Als Kommando, welches alle Dateien anzeigt welche entweder V oder v anzeigen, weiterhin Vorlesung gefolgt von irgendwelchen Informationen darstellt. und diese von 2000 bis 2029 heraussuchen kann. Das heißt wir haben eine große Menge von Wörtern mit einem einzigen Ausdruck definieren und beschreiben können.

Definition - Reguläre Ausdrücke :

Nenne die Definition eines regulären Ausdruckes unter der Prämisse, dass $\Sigma$ ein Alphabet beschreibt. Welche speziellen Fälle treten weiterhin auf? #card Sei $\Sigma$ ein Alphabet. Dann sind $\varnothing$ und $ϵ$ reguläre Ausdrücke, obwohl sie leer sind ($\varnothing$ leere Sprache, $ϵ$ leeres Wort) Weiterhin sind Alle Buchstaben aus $\Sigma$ reguläre Ausdrücke.

[!Definition] regulärer Ausdruck was wird benötigt, welche drei Grundlagen können wir daraus bilden? #card

Sei ferner $\Sigma$ ein Alphabet, dann gilt für dieses folgend (um eine regex zu bilden):

• $\varnothing$ - die leere Sprache, aber auch $\epsilon$ - leeres Wort bilden jeweils reguläre Ausdrücke
• alle Buchstaben $x\in \Sigma$ sind reguläre Ausdrücke Ferner können wir jetzt drei Grundlagen für die regulären Ausdrücke festlegen/ definieren, Seien dafür $R_1,R_2$ reguläre Ausdrücke, dann sind auch die folgenden wieder reguläre Ausdrücke:

1. $R_1\cup R_2$ –> Vereinigung, beschrieben mit $a\mid b$
2. $R_1\circ R_2$ –> Verkettung beschrieben mit $ab$
3. $R_1^{\ast }$ –> der Kleen’sche Abschluss, beschrieben mit $[a{]}^{\ast }$

Hieraus können wir ferner verschiedene Operationen - alle möglichen - umsetzen. –> Diese drei Operatoren bilden ein Operatorensystem

Erweiterung | syntactic sugar

Da diverse Operationen in ihrer Notation sehr aufwendig werden können, wollen wir ferner diverse Abkürzungen definieren, die dabei helfen, diverse Strukturen einfacher zu beschreiben.

[!Tip] $?$ wie kann man es mit den drei grundlegenden Operatoren darstellen? #card

$?$ erkennt ob das vorherige Zeichen $0\vee 1$ vorkommt: Also $a?\to a\vee \epsilon$ anders dargestellt wäre es: $$a?=a\cup \epsilon$$

[!Tip] $+$ wie kann man es mit den drei grundlegenden Operatoren darstellen? #card $+$ erkennt 1 oder mehrer Vorkommen eines vorherig genannten Zeichens. Also wird $a+⟹a,aa,aaa,\dots$ erkennen. anders beschrieben mit $a+=a\circ a^{\ast }$

[!Attention] $.$ wie kann man es mit den drei grundlegenden Operatoren darstellen? #card

Mit $.$ geben wir an, dass ein beliebiges Zeichen des Alphabets erkannt werden kann. Also wird $.=a,b,c,d,\dots$ und anders beschrieben als: $.=\Sigma -a\cup b\cup \cdots \cup z$

[!Information] $[\wedge abcd]$ wie kann dieser Ausdruck mit grundlegenden Operatoren dargestellt werden? #card Mit [^abcd…] wird eine Verneinung beschrieben, also die Zeichen, die in der Klammer genannt werden, nicht erkannt. Ferner können wir folgenden Operator also so umschreiben: $$[\wedge abc]=\Sigma \setminus \{a,b,c\}=d\cup e\cup \cdots \cup z$$

[!Information] $x\{n,m\}$ wie kann dieser Ausdruck mit grundlegenden Operatoren dargestellt werden? #card Dieser Operant wird genutzt, um $n-m$ Vorkommen des vorherigen Zeichens erkennen zu können. Das heißt es ist ähnlich zur Wiederholung mit $\ast \vee +$ jedoch mit einem gegebenen Intervall! Dargestellt werden kann es aus einer Konkatenation aller Wiederholungen, die erlaubt sind: $$a\{2,4\}=aa\cup aaa\cup aaaa$$

[!Information] $x\{n\}$ wie kann dieser Ausdruck mit grundlegenden Operatoren dargestellt werden? #card Mit diesem Operant erkennen wir, wie im vorherigen, die $n$-malige Wiederholung des vorangegangenen Wortes. Ferner entspricht dieser Ausdruck dann folgender Darstellung: $$a\{3\}=aaa$$

Beispiele :

Der Ausdruck $0\ast 10\ast$ beschreibt hiermit alle Ausdrücke, die (welche Ausdrücke gehören dazu?) :: anfangs beliebig viele 0 beinhaltet, dann von einer 1 gefolgt wird und anschließend noch beliebige 0 an gehangen werden können. Damit werden also 00100000, 010, 10, 00100 etc. beschrieben

[!Tip] Konvention der Chronologie von Konkatenationen #card

Wie bei anderen System, gelten hier auch Konventionen zur Chronologie der Verarbeitung: Zuerst $\ast$, dann $\circ$, dann $\cup$

Algebraische Regeln :

Seien $E,F,G$ reguläre Ausdrücke. Dann gelten unter Betrachtung der Konkatenation : welche algebraischen Regeln? #card

• $\cup$ ist diese Assoziativ, kommutativ und hat $\varnothing$ als neutrales Element.
• $\circ$ ist assoziativ, nicht kommutativ, hat $ϵ$ als neutrales Element. Distributivgesetz: $(E\cup F)\circ G=E\circ G\cup F\circ G$ $E\circ (F\cup G)=E\circ F\cup E\circ G$ Die Erzeugung einer Kleene’schen Hülle von einer Kleene’schen Hülle, resultiert mit der gleichen Kleene’schen Hülle: $(E^{\ast }{)}^{\ast }=E^{\ast }$ ${\varnothing }^{\ast }=ϵ$–> Alle Wörter, die wir aus einer leeren Menge bilden können, sind leere Wörter ${ϵ}^{\ast }=ϵ$ selbiges Prinzip bei Verwendung eines leeren Wortes

Induzierte Sprache $L(R)$

Die von $R$ - also einem regulären Ausdruck - induzierte Sprache $L(R)$ beschreibt also die Menge welche alle möglichen Wörter beschreibt, welche unter Anwendung des regulären Ausdruckes beschrieben werden können. Das heißt, wie obig alle möglichen Beispiele, die bestimmte Wörter beschreiben können. welche Schlüsse können wir daraus ziehen, wie wird eine induzierte Sprache nun definiert? Sei $R$ ein regulärer Ausdruck. Dann ist die von $R$ induzierte Sprache $L(R)$ folgend definiert: #card $R=\varnothing ⟹L(R)=\varnothing$ $R=ϵ⟹L(R)=\{ϵ\}$ $R=\omega$ für ein $\omega \in \Sigma ⟹L(R)=\{\omega \}$
$R=R_1\cup R_2⟹L(R)=L(R_1)\cup L(R_2)$ –> Ein regulärer Ausdruck, welcher sich aus mehreren zusammenfasst, kann genauso aufgegliedert werden. $R=R_1\circ R_2⟹L(R)=L(R_1)\circ L(R_2)$, $R=R_1^{\ast }⟹L(R)=(L(R_1){)}^{\ast }$ –> wir können hiermit und durch die Konkatenation dieser Sprachen dann wahrscheinlich auch die ganzen anderen regulären Sprachen erkennen, die wir sonst mit einer normalen Sprache, wie wir sie in 112.03_reguläre_sprachen definiert haben!

[!Attention] reguläre Sprache $\leftrightarrow$ regulärer Ausdruck Wir werden herausfinden / wissen, dass die Sprachen, die reguläre Ausdrüçke beschreiben können, die gleiche Menge abdecken wird, die durch reguläre Sprachen - also wenn wir sie mit einem finite state automata darstellen können - abdeckt.

Aus dieser Betrachtung heißt das also, dass wir Regex mit einem Automaten darstellen können! Und das heißt, dass wir sie mit Maschinen umsetzen und verwenden können.

Satz - Regulärer Ausdruck $⟺$ reguläre Sprache

was besagt diese Aussage? #card Eine Sprache ist genau dann regulär, wenn - nur dann tatsächlich - sie durch einen regulären Ausdruck beschrieben wird. ( werden kann). Sie muss durch eine reguläre 112.08_grammatiken beschrieben werden (können). Beweisen kann man diese Struktur durch das Betrachten beider “Richtungen” $\Leftarrow ,\Rightarrow$ und daraus lassen sich zwei Lemmata bilden!

Lemma 1 | Sprache durch regex –> ist regulär:

[!Lemma] Lemma 1 | Sprache durch regex –> ist regulär: Wenn eine Sprache durch einen regulären Ausdruck beschrieben wird, dann ist sie regulär!, also $\in REG$

Konstruktion von RegEx zu NFA | DFA

Beweis | Sprache durch regrex beschrieben -> regulär

Dafür hat Kleene einen entsprechenden Beweis geliefert:

Es wird eine strukturelle Induktion angewandt:

Induktionsanfang: IA: Alle Sprachen der Länge $0\vee 1$ Falls $R=a,a\in \Sigma :L(R)=\{a\}$ -> also wir können einen Automat $A$ konstruieren, der die Regex $R$ erkennt! Folgend etwa: Ist $R=\epsilon$, dann gilt nach Definition - die wir zuvor betrachtet haben - $L(R)=\{\epsilon \}$ und ferner gibt es einen Automat, der $B$ als Regex erkennen kann. Folgend etwa; Falls $R=\varnothing$ dann gilt nach Definition $L(R)=\varnothing$ und wir können wieder einen Automat $C$ beschreiben, der die Regex $R$ erkennt. Folgend etwa:

Konstruieren wir ferner die Induktionsannahme:

Induktionsannahme: Sei jetzt $R_1,R_2$ reguläre Ausdrücke, für die wir bereits FAs konstruiert haben - kennen.

Induktionsschluss: Mit der Grundlage der vorherigen FAs für die grundlegenden Strukturen von $R$ - Regex - können wir jetzt für folgende Strukturen andere FAs konstruieren (durch elementare Operationen):

• $R_1\cup R_2$, denn $REG$ ist under $\cup$ abgeschlossen!
• $R_1\circ R_2$ weil $REG$ unter $\circ$ abgeschlossen ist!
• $R_1^{\ast }$, denn $REG$ ist under ${}^{\ast }$ abgeschlossen. –> Daraus folgt dann ferner: $L(R_1\cup R_2),L(R\circ R_2),L(R_1^{\ast })\in REG$!

Lemma 2 | Sprache ist regulär –> $\exists R\in \text{RegEx}$ die die Sprache beschreibt.

[!Lemma] Lemma 2 | Sprache ist regulär –> $\exists R$ die die Sprache beschreibt. Wenn eine Sprache regulär ist, dann wird sie durch einen regulären Ausdruck beschrieben.

Beweisidee | Sprache ist regulär –> $\exists R$ die die Sprache beschreibt.

[!concept] Konzeptueller Beweis: Als Konzept möchten wir den Automaten so aufteilen, dass wir sie in klein klein Regex aufsplitten können und so dann viele kleine RegEx für eine Verbindung von $i\to j$ bilden ( das soll für alle Paare gelten!) und dadurch kann man die einzelnen Teile damit darstellen. Anschließend muss man jetzt diese einzelnen RegEx nachfolgend verknüpfen, um daraus den entsprechenden Ausdruck bilden zu können

Sei dafür jetzt ein Automat, der eine Sprache $L$ erkennt: $M=(Q,\Sigma ,\delta ,q_0,F)$ Ohne Beachtung des Allgemeinen: Der Automat hat folgende Zustände $Q=\{1,\dots ,n\},q_0=1$ Wir möchten jetzt zwei beliebige Zustände $i,j$ anschauen ( $\in Q$). Wir suchen jetzt alle Worte mit denen $M$ von $i\to j$ übergeht (also wir schauen, welche Wörter diesen beschriebenen Übgergang aufweisen/haben). Das ist durch eine Induktion möglich: Betrachten wir dafür die Menge von Zwischenzuständen bei dem Übgergang von $i\to k\to j$. Für den Anfang: $k=0$ und somit suchen wir nur die Worte mit direktem Übergang von $i\to j$ ( diese Beschreiben ferner eine Klasse von Wörtern: $E_{ij}^0$) –> wir wollen jetzt die Menge aller Klassen $E_{ij}^n$ finden, die quasi Wörter mit bis zu $n$ Übergängen akzeptiert. Ferner also: $$\begin{array}{r}k=1,i\to j:E_{ij}^1\\ k=2,i\to j:E_{ij}^2\\ ⋮\\ k=n,i\to j:E_{ij}^k\end{array}$$ Aus dieser Betrachtung können wir jetzt ferner die Sprache konstruieren: $$L(E_{ij}^n)=\{w\mid {\delta }^{\ast }(i,w)=j\}$$ Also die obig benannte Menge an Übergängen, um Worte von Zustand $i\to j$ beschreiben zu können! Ferner können wir die Menge von Wörtern, also die Sprache, die der Automat erkennt folgend zusammenfassen: $$L(M)=\bigcup _{q_f\in F}L(E_{1q_f}^n)$$ Wir beschreiben mit diesem Term also den regulären Ausdruck, der den Automaten darstellen/beschreiben kann. Das beschreibt die konzeptuelle Idee hinter dem Beweis dieser Äquivalenz, jedoch müssen / wollen wir es entsprechend formalisieren!

Beweis | Sprache ist regulär –> $\exists R$ die die Sprache beschreibt.

Aus vorheriger Betrachtung haben wir nun wieder einen Automaten $M=(Q,\Sigma ,\delta ,q_0,F):L(M)$ der eine Sprache $L$ erkennen kann. Wir definieren wieder Ohne Beachtung der Allgemeinheit die Zustände $Q=\{1,2,\dots ,n\},q_0=1$ als Zustände des Automaten - es ist quasi egal, wie wir sie da definieren / bezeichnen.

Wir können nun induktiv die einzelnen regulären Ausdrücke $E_{ij}^k$ konstruieren, die folgende Eigenschaft einhalten:

[!Important] Voraussetzung: $$L(E_{ij}^k)=\{w\mid {\delta }^{\ast }(i,w)=j\wedge \forall \text{ Pra¨fixe von w },w^{\prime }\ne \epsilon \wedge w^{\prime }\ne w:{\delta }^{\ast }(i,w^{\prime })\le k\}$$ Wir setzen also eine Voraussetzung, das wir ein Wort betrachten, welches ein Präfix, was nicht leer und weiter nicht gleich dem Wort selbst ist, aufweist, und sagen dafür aus, dass die erweiterte Übergangsfunktion vom Start $i$ zu diesem Präfix kleiner als die Menge an Zustandssprüngen, die wir erlauben $(k)$ ist. Also ${\delta }^{\ast (i,w^{\prime })}\le k$

Unter dieser Betrachtung können wir nun den Anfang der Induktions beschreiben: Induktionsanfang: Sei dafür $k=0$, also wir haben keinen Zwischenzustand zwischen den Übergängen, also wir betrachten nur die direkten Übergänge von $i\to j$ Wir betrachten zwei Fälle:

• Sei $i\ne j$ .Falls es einen direkten Link von $i\to j$ gibt, seien dann ${\sigma }_1,\dots {\sigma }_t\in \Sigma$ die Buchstaben auf diesem direkten Link ( die also den direkten Übergang ermöglichen!) Dann können wir jetzt $E_{ij}^0={\sigma }_1\cup \cdots \cup {\sigma }_t$ als die “Reguläre Expression” setzen, um von diesen Punkt zum nächsten zu kommen! (Also wir sagen aus, was es brauch um von einem Punkt zum nächsten zu kommen. Dabei sind die erlaubten Symbole als eine Vereinigung zu betrachten, um so die RegEx bilden zu können!) Wenn es keinen direkten Link gibt, setzen wir $E_{ij=\varnothing }^0$
• Sei jetzt $i=j$. Falls es einen direkten Link - zu sich selbst, also ein Cycle - gibt, seien dann ${\sigma }_1,\dots {\sigma }_t\in \Sigma$ die Buchstaben auf diesem Link ( die den Übergang erlauben!) Wir können jetzt wieder die Regex beschreiben mit : $E_{ij}^0=\epsilon \cup {\sigma }_1\cup \cdots \cup {\sigma }_t$ Wenn es keinen direkten Link gibt, setzen wir ferner einfach $E_{ij}^0=\epsilon$ Aus dieser initialen Betrachtung ist die obige Voraussetzung erfüllt:

Induktionsannahme: Seien jetzt alle $E_{ij}^{r}0\le r\le k,\forall i,j,\in Q$ so konstruiert, dass dann die Voraussetzung erfüllt wird.

Induktionsschritt: Aus dem obigen Anfang und der Annahme können wir jetzt folgende Konstruktion durchsetzen: Wir konstruieren jetzt für alle Kombinationen von $i,j\in Q$ die entsprechenden Mengen $E_{ij}^{k+1}$ folgend: $$\stackrel{\text{vorherige Menge}}{\overbrace{E_{ij}^{k+1}=E_{ij}^k}}\cup \stackrel{\text{ neue Struktur}}{\overbrace{E_{i,k+1}^k\cdot (E_{k+1,k+1}^k{)}^{\ast }\cdot E_{k+1,j}^k}}$$ (Also wir konstruieren die nächste Menge indem wir zuvor bekannte Menge von Sprüngen $k$ von $i\to j$ betrachtet haben und für die nächsten Sprünge werden wir also einfach die alten Zustände nehmen und den neuen Pfad konstruieren, indem wir von dem alten Zustand $i\to k$ über den neuen Zustand, also $k\to k+1$ zu unserem Zielzustand springen, also $k+1\to j$ Dadurch lässt sich jetzt der neue Sprung beschreiben). Grafisch folgende Idee:

Durch dies Struktur wird jetzt die Konstruktion erfüllt und wir können den Automaten als eine Regex darstellen!

((Alternativer Beweis, den man in Sippser finden kann!)) Dafür definiert man in dem Kontext dann einen GNFA - generalisierter nichdeterministischer endlicher Automat.

Betrachten wir dafür noch ein Beispiel:

Beispiel der Anwendung | Automat als RegeEx

betrachten wir folgenden Automaten:

stateDiagram-v2
	Direction LR
[*] --> 1
1 --> 1:a,b
1 --> 2:b
2 --> 3:a,b
1 --> 3:b

Wir können jetzt hier $\forall i,j\in Q:E_{ij}^{k+1}$ mit $E_{i,j}^{k+1}=E_{i,j}^k\cup E_{i,k+1}^k\cdot (E_{k+1,k+1}^k{)}^{\ast }\cdot E_{k+1,j}^k$ Also wieder die Verbindung aus dem alten Zuständen mit einem bestimmten $k$ mit den neuen Zuständen, die von den alten ausgehen und dann aber ein anderes Ziel $k+1$ anstreben.

Dafür müssen wir jetzt also einfach alle möglichen Kombinationen berechnen und anschließend vereinigen!: $$\begin{array}{rlr}{E}_{11}^0& =\epsilon \cup a\cup b& \text{ von 1 zu 1 ohne Sprung zu anderen!}\\ E_{1,2}^0& =b& \\ E_{1,3}^0& =b& \\ R_{22}^0& =\epsilon =E_{22}^1& \\ E_{11}^1& =(\epsilon \cup a\cup b{)}^{\ast }=E_{11}^2=E_{11}^3& \text{ Es nimmt alte Zusta¨nde und fu¨gt neue hinzug}\\ E_{12}^1& =(a\cup b{)}^{\ast }\cdot b=E_{12}^2=E_{12}^3& \\ E_{13}^1& =b\cup (a\cup b{)}^{b}b& \text{ vereinigt also }{E}_{13}^0\cup E_{1,4}^0\cdot (E_{2,4}^0{)}^{\ast }\cdot E_{2,3}^0\\ E_{23}^0& =a\cup b=E_{23}^1& \end{array}$$

Damit können wir jetzt die volle Vereinigung erzeugen: $$\begin{array}{rl}{E}_{13}^2& =E_{13}^1\cup E_{12}^1(E_{22}^1{)}^{\ast }{E}_{23}^1\\ & =(b\cup ((a\cup b{)}^{\ast }b))\cup (a\cup b{)}^{\ast }b(\epsilon {)}^{\ast }(a\cup b\\ & =(b\cup ((a\cup b{)}^{\ast }b))\cup (a\cup b{)}^{\ast }b(a\cup b)=E_{13}^3\end{array}$$ Wir haben hier jetzt alle möglichen Übergänge vom Anfangs zum Zielzustand beschrieben, und dabei alle möglichen Kombinationen betrachtet und vereinigt!

[!Tip] Wenn wir hier von “Unter Verwendung von $X$” beschrieben mit $E_{ij}^X$ meinen wir, dass wir über einen bestimmten Zustand traversieren möchten!. Der Pfad von $i\to j$ muss also über $X$ Sprünge verlaufen! Das fordert die Konstruktion dieser RegEx!

Definition | GNFA = Generalisierter nichtdeterministischer endlicher Automat

Im Beweis von Kleenes Algorithmus - [Satz - Regulärer Ausdruck $Longleftrightarrow$ reguläre Sprache](#Satz%20-%20Regulärer%20Ausdruck%20%20reguläre%20Sprache) - ist die generalisierte Übergangsfunktion ${\delta }^{\ast }$ sehr wichtig/ zentral. Wir können diese unter der Definition eines Generalisierten nichtdeterministischen endlichen Automaten formaler präziser beschreiben.

Wir werden GNFAs folgend so definieren, dass sie keine Übergänge auf $q_{\text{start}}$ haben und somit auch keine Übergänge von $q_{\text{accept}}$ wegen haben werden. Sonst haben sie von jedem Zustand zu einem anderen einen Übergang!

[!Definition] GNFA Wir beschreiben einen generalisierten nichtdeterministischen endlichen Automaten (GNFA) wieder mit einem 5-Tupel:

$$M=(Q,\Sigma ,\delta ,q_0,F)$$ wobei wir folgend beschreiben: $Q=$ endliche Menge von Zuständen $\Sigma =$ Alphabet $\delta$ ist die Übergangsfunktion mit folgender Definition: $$\delta :(Q\setminus \{q_{\text{ accept}}\})\times (Q\setminus \{q_{\text{start}}\})\to REG$$ Ferner beschreiben wir mit $q_{\text{ start}}$ den Start und $q_{\text{accept}}$ Endzustand

Besonderheit Übergangsfunktion:

Die Definition von $\delta$ legt fest, dass wir, wie obig beschrieben, keinen Pfeil, der zum Start zeigt und keinen Pfad der vom Ende wegzeigt haben werden.

Die Übergänge werden mit REGEX, als regulären Ausdrücken beschrieben!

Berechnung |

Wir möchte noch anschauen, wann ein GNFA ein Wort akzeptiert oder nicht:

[!Important] $w\in GNFA$ | Berechnung Wir sagen, dass ein GNFA ein Wort $w=w_1,w_2,\dots ,w_k$ mit $w_i\in \Sigma$ genau dann akzeptiert, wenn es eine Folge von Zuständen gibt, von $q_0,q_1,\dots ,q_k$ sodass:

• $q_0=q_{\text{start}}$
• $q_k=q_{\text{accept}}$
• $\forall i=1,\dots ,k:w_i\in L(\delta (q_{i-1},q_i))$ Also $w_i$ ist in der Sprache des regulären Ausdrucks ( der den Übergang beschreibt!) des Übergangs von $q_{i-1}\to q_i$

Folgerungen aus GNFAs | $\forall DFA=\exists GNFA$

Wir möchten jetzt zeigen, warum jeder DFA zu einem GNFA überführt werden kann:

Man kann mit GNFAs wieder zeigen, dass eine reguläre Sprache - als Automat - mit einer RegEx dargestellt werden kann. (Also genau diese Übertragung von DFA( hat Automat!) zu GNFA (hat RegEx in seiner Übergangsfunktion))

[!Important] Ansatz zur Überführung:

1. Füge einen neuen Startzustand $q_{\text{start}}$ hinzu, der mit einem $\epsilon$-Übergang auf den alten Startzustand zeigt. - denn $\epsilon \in REG$
2. Füge einen neuen Endzustand $q_{\text{accept}}$ hinzu, von dem alle alten Endzustände mit $\epsilon$-Übergängen erreicht werden ( ähnlich zu Aufgabe 4a)
3. Wir ersetzen jetzt alle Übergänge durch reguläre Ausdrücke. Übergänge mit mehrerenBuchstaben werden dann durch eine vereinigung von Regex, als $\cup \in REG$ dargestellt. Übergänge mit nur einem Buchstabe übernehmen diesen (ist ja immernoch Regex)
4. Wir fügen alle fehlenden Übergänge hinzu und markieren sie mit $\varnothing \in REG$ (also quasi die nicht relevanten Übergänge, damit alles abgedeckt wird). Durch diesen Schritt wird die Sprache von $M$ nicht verändert, da solche $\varnothing$ Übergänge nicht genommen werden.

Beweis | Konstruktion GNFA von DFA

[!Tip] Konstruktion von $E_{ij}^k$ ist formal die Reduktion eines GNFA

Ansatz: Als Beweisidee möchten wir folgend vorgehen: Das können wir diesmal über die Größe des Zustandraumes $\mid Q\mid =k$ betrachten und dadurch dann den Automat nach und nach aufteilen und in REG umformen / verkleinern.

Wir wollen hier konzeptuell den Automaten nach und nach verkleinern - bis wir nur noch start und end Zustände haben - und dadurch werden wir die Übergänge immer weiter kombinieren / verdichten, sodass im Endzustand eine einzige Bedingung die als REGEX angibt, wie man vom Start in den Endzustand kommt!

–> In jedem Schritt nehmen wir also einen Zustand heraus und versuchen dann den leeren Übergang - also Kante ohne Knoten als Ziel - in einen anderen Zustand zu mergen und somit auch die Übergangsfunktion dessen zu erweitern bzw so zu adaptieren, dass dann ein Übergang möglich ist.

Wenn ein GNFA genau $k=2$ Zustände hat - den start und endzustand! - dann ist der reguläre Ausdruck dieser Sprache - bzw der von diesem GNFA beschrieben wird - gleich dem Übergang von start zum ende –> danach fertig.

Wenn ein GNFA nun $k>2$ Zustände hat, müssen wir anderweitig verfahren: Wir nehmen einen beliebigen Zustand $q_{\text{ rupf}}$ und “rupfen” diesen jetzt aus dem Automaten. Anschließend reparieren wir ihn so, dass die Kanten zu dem Zustand zusammengefasst in einen anderen Zustand gehen –> wir dafür also eine RegEx basteln. Wir konstruieren hier also $E_{ij}^k$

Wie wir bereits aus der vorherigen Betrachtung wissen:

[!Tip] Jede reguläre Sprache $L$ wird von einem regulären Ausdruck beschrieben.

Formaler Beweis:

Sei jetzt $M(L)$ der DFA, der die Spraceh $L$ erkennen kann. Wir wollen jetzt einen äquivalenten GNFA unter Betrachtung der vorherigen Konstruktion bauen:

[!Definition] Wir Verwenden dafür den CONVERT Algorithmus um den regulären Ausdruck zu finden, der die Sprache $L$ beschreibt ( also $E_{ij}^k$). wie ist der CONVERT Algorithmus aufgebaut? #card

Sei jetzt folgend: $k=|Q\mid$ die Zahl der Zustände $Q$. Wir betrachten jetzt folgende Fälle:

1. Falls $k=2$ dann ist $Q=\{q_{textstart},q_{\text{accept}}\}$. Gebe jetzt den RegEx $R=\delta (q_{\text{start},q_{\text{accept}}})$ an. Danach sind wir fertig!
2. Falls $k>2$ wählen wir einen beliebigen Zustand $q_{\text{rupf}}$ (ungleich Start/End) $\in Q\setminus \{q_{\text{start}},q_{\text{accept}}\}$. Wir erzeugen jetzt einen GNFA: $$G^{\prime }=(Q^{\prime },\Sigma ,{\delta }^{\prime },q_{\text{start},q_{\text{accept}}})$$ mit $Q^{\prime }=Q\{\setminus q_{\text{rupf}}\}$ und die Übergangsfunktion wird angepasst: ${\delta }^{\prime }(q_i,q_j)=(R_1)(R_2{)}^{\ast }(R_3)\cup R(4),\forall q_i\in Q^{\prime }\setminus \{q_{\text{accept}}\},q_j\in Q^{\prime }\setminus \{q_{\text{start}}\}$ (Eigenschaft, dass start und ende nicht erreicht / verlassen wird) Ferner beschreiben wir hier: $R_1=\delta (q_j,q_{\text{rupf}}),R_2=\delta (q_{\text{rupf}},q_{\text{rupf}}),R_3=\delta (q_{\text{rupf}},q_j),R_4=\delta (q_i,q_j)$ Wir setzen weiter $G=G^{\prime }$ und weiterhin $k=k-1$ (also reduzieren Schritt für Schritt!) Wir Wiederholen jetzt nochmals. Behauptung: Via Induktion zeigen wir, dass $G$ unter Anwendung des Algorithmus $CONVERT(G)$ umgewandelt werden kann und G und das Ergebnis äquivalent sein wird. Für $k=2$ ist die Aussage offentsichtlich.

Sei jetzt $k>2$, und es gelte die Behauptung für $k-1$:

1. Sei $w$ ein Wort, das von $G$ akzeptiert wird. Dann gibt es eine akzeptierende Folge von Zuständen $q_{\text{start}},q_1,\dots ,q_{\text{accept}}$. Falls diese Folge $q_{\text{rupf}}$ nicht enthält, dann wird $w$ auch von $G^{\prime }$ akzeptiert. Falls diese Folge $q_{\text{rupf}}$ enthält, seien $q_i,q_j$ die Nachbarinnen dieses Zustands in der Folge. Dann enthält jetzt $G^{\prime }$ eine akzeptierende Regel in ${\delta }^{\prime }(q_i,q_j)$ entweder direkt oder über $q_{\text{rupf}}$. In beiden Fällen wird das Wort von $G^{\prime }$ akzeptiert ( wir haben ja den Pfad übernommen und angepasst).
2. Sei nun umgekehrt $w$ ein Wort, dass von $G^{\prime }$ akzeptiert wird. Dann gibt es eine akzeptierende Regel in ${\delta }^{\prime }(q_{\text{start}},q_{\text{accept}})$ entweder direkt, oder über $q_{\text{reupf}}$. Auch hier wird $w$ in beiden Fällen von $G$ akzeptiert.
3. Dadurch ist die Äquivalenz gezeigt, wenn man dem Prozedere folgt, um so nach und nach einen Automaten zu transformieren.

Ausblick |

Man sieht hier schon, dass eine unendliche reguläre Sprache trotz ihrer unendlichen Menge von Worten dennoch durch eine RegEx beschrieben werden kann. Das lässt uns ferner herausfinden, dass diese Sprachen dann die Limitierungen von RegEx haben wird –> Beispielsweise nicht zählen kann!

Weiterführende Themen:

• 112.06_nicht_reguläre_Sprachen