date-created: 2024-04-30 12:22:25 date-modified: 2024-05-07 10:01:52

$\exists$ nicht reguläre Sprachen |

anchored to 112.00_anchor_overview proceeds from and requires 112.05_regular_expressions 112.03_reguläre_sprachen

Overview | Gibt es nicht reguläre Sprachen?

Vermutlich ja! -> wir haben ja gesehen, dass endliche AUTOMATEN DFAS und NFAS kein großes Gedächtnis haben. Wir können hier etwa erkennen, dass diese Automaten nicht zählen können!

Ferner betrachten wir eine beispielhafte Sprache, welche nicht durch einen NFA / DFA oder einer RegEx dargestellt werden kann: $$L=\{0^n{1}^n\mid n\in \mathbb{N}\}=\{01,0011,000111,\dots \}$$ Warum diese Sprache nicht erkannt werden kann? Sie muss zählen können, was man mit kleinen Quantitäten vielleicht noch kann (einfach für jede Möglichkeit einen Zustand und dann am Ende einen akzeptierenden), aber wir wollen das hier für beliebige Zahlen $\in \mathbb{N}$ ermöglichen! Das ist mit einer endlichen Zustandsmenge nicht möglich!

[!Important] Muster in regulären Sprachen Betrachten wir eine reguläre SPrache, dann haben wir bei diesen meist ein Muster, was beliebige Mengen / oder eindeutige Mengen konkateniert mit anderen darstellt. Ferner werden wir kein Muster sehen, dass uns etwa zählen lassen wird/muss, um ein Wort zu konstruieren.

Finden von nicht regulären Sprachen?

Wir wissen also, dass es einen Raum gibt, der scheinbar nicht regulär sein kann. Dieses Konzept möchten wir ferner unter Betrachtung des Pumping-Lemmas beweisen können.

[!Tip] Grundlagen

Wir gehen davon aus, dass es nicht reguläre Sprachen gibt.

Als Grundlage haben wir folgende Eigenschaften und Informationen:

welchen zwei Aspekte können wir über Sprachen in REG treffen? #card

• Jede Sprache $L\in REG$ wird von einem endlichen regulären Ausdruck beschrieben
• Jedes Sprache $\in REG$ kann man auch mit einem DFA / NFA darstellen ( beide sind gleichwertig)

Unter Betrachtung dieser Prämisse möchten wir dann jetzt das Pumping-Lemma betrachten, welches zeigen kann, dass eine Sprache nicht regulär ist (und somit nicht von einem DFA /NFA entschieden werden kann)

Hieraus können wir folgende Idee schöpfen: 112.07_pumping_lemma

[!Attention] Fähigkeit vom Pumping Lemma Das Pumping-Lemma liefert nur die Möglichkeit zu zeigen, dass eine Sprache nicht regulär ist ( nichts weiteres ist möglich)

vollständige Charakterisierung von $REG$

Wir möchten schauen, ob es ein vollständiges Kriterium gibt, mit welchem wir jetzt die Regulären Sprachen charakterisieren könnten/können.

unterscheidende Erweiterung (einer Sprache)

Wir möchten für die obige Vermutung / Suche jetzt eine neue Definition einführen:

[!Definition] Kongruenz | unterscheidende Erweiterung

Sei eine Sprache $L$ über $\Sigma$ und ferner $x,y\in {\Sigma }^{\ast }$ (beide müssen nicht in der Sprache sein!) Wir nennen jetzt ein weiteres Wort $z\in {\Sigma }^{\ast }$ unterscheidende Erweiterung, wenn gilt:

Welche zwei Attribute müssen gelten? Wann nennen wir die Worte dann kongruent? #card

1. $xz\in L\wedge yz\notin L$ oder
2. $zx\notin L\wedge yz\in L$ Es muss also in der Kombination mit einem anderen Wort in der Sprache enthalten sein!

Ferner bezeichen wir dabei jetzt zwei Worte $x,y$ als (nerode)kongruent und beschreiben sie mit $x{\sim }_{L}y$ gen dann, wenn es für diese beiden Wort keine unterscheidende Erweiterung gibt. Das heißt jetzt also ferner: $$x{\sim }_{L}y⟺\forall z\in {\Sigma }^{\ast }:xz\in L⟺yz\in L$$ und somit auch: $$x\in L⟺y\in L$$

[!Tip] Äquivalenzrelation Ferner ist die Struktur jetzt eine Äquivalenzrelation, denn folgende Attribute werden eingehalten welche 3? #card Reflexiv: $x{\sim }_{L}x,\forall x\in L:\forall z\in {\Sigma }^{\ast }:xz\in L=xz\in L$ Symmetrisch: $x{\sim }_{L}y⟺y{\sim }_{L}x$ (ähnliches Argument wie obig, kann man umstellen) transitiv: $x{\sim }_{L}y\wedge y{\sim }_{L}z\to x{\sim }_{L}z$, ferner also: $\forall c\in {\Sigma }^{\ast }:xc\in L=yc\in L=zc\in L$ und somit gilt die entsprechend Äquivalenz

[!Attention] Es können somit Äquivalenzklassen aufgebaut werden!

Theorem | Myhill-Nerode

Aus der obigen Vorbetrachtung können wir jetzt ein neues Theorem betrachten - von Myhill-Nerode:

[!Definition] Theorem | Myhill-Nerode was besagt es? #card Eine Sprache $L$ ist regulär, genau dann, wenn sie endlich viele Äquivalenzklassen unter ${\sim }_L$ aufweist. Diese endliche Zahl an Äquivalenzklassen, was den Index von ${\sim }_L$ beschreibt, ist dann genau die Anzahl an Zuständen des minimalen deterministischen endlichen Automaten, der diese Sprache $L$ erkennen kann! –> Er ist damit also eindeutig ( wobei es Isomorphe Automaten geben kann).

Beweis des Theorem

Da es eine Äquivalenz ist, muss man hier auch beide Seiten beweisen.

Beweis: $⟹$ Sei $L$ eine reguläre Sprache und $M=(Q,\Sigma ,\delta ,q_0,F)$ ein DFA mit $L=L(M)$ Wir möchten jetzt eine Äquivalenzrelation $x{\sim }_{M}y$ betrachten. Es gilt $x{\sim }_{M}y$ genau dann, wenn ${\delta }^{\ast }(q_0,x)={\delta }^{\ast }(q_0,y)$ – also der Automat auf $x,y$ zu den gleichen Zuständen übergeht. Wir haben dann hier eine erste offentsichtliche Äquivalenzrelation gefunden!

[!Tip] $=$ ist auch eine Äquivalenrelation!

Wir zeigen jetzt, dass $x{\sim }_{M}y⟹(x{\sim }_{L}y)$ impliziert, also eine weitere Äquivalenzrelation. Sei demnach dann $x{\sim }_{M}y$, also wieder ${\delta }^{\ast }(q_0,x)={\delta }^{\ast }(q_0,y)$. Für ein beliebiges $z\in {\Sigma }^{\ast }$ folgt jetzt: $$\begin{array}{rlr}xz\in L& ⟺{\delta }^{\ast }(q_0,zx)\in F& ⟺{\delta }^{\ast }({\delta }^{\ast }(q_0,x),z)\in F\\ & ⟺{\delta }^{\ast }({\delta }^{\ast }(q_0,y),z)\in F& ⟺{\delta }^{\ast }({\delta }^{\ast }(q_0,yz))\in F\\ & & ⟺yz\in F\end{array}$$ und somit haben wir die Translation gezeigt!

Wenn jetzt $x{\sim }_{M}y⟹x{\sim }_{L}y$, dann hat die Äquivalenzrelation ${\sim }_M$ mindestens den Index von ${\sim }_L$ - also wir können die Kleen’sche Hülle in gleich viel Klassen aufteilen!. –> Aber der Index von ${\sim }_M$ ist die Zahl der Zustände, die von $q_0$ aus erreichbar sind. Demnach sind sie höchstens: $\mid Q\mid <\infty$

Ferner noch der Beweis in die andere Richtung

Beweis: $⟸$ Wenn der Index von ${\sim }_L$ endlich ist, dann gibt es endlich viele Wörter $x_1,x_2,\dots ,x_k$ sodass ${\Sigma }^{\ast }=[x_1]\cup [x_2]\cup \cdots \cup [x_k]$ die Konkatenation der Äquivalenzklassen ist!. Wir definieren dann einen Automaten $M_0$ der genau diese Klassen als die Zustände aufweist: $$\begin{array}{rlr}{M}_0& :=(Q,\Sigma ,\delta ,q_0,F)& \\ Q& =\{[x_1],[x_2],\dots ,[x_k]\}& \\ \delta ([x],a)& =[xa]& \text{ die A¨quivalenzklasse die diese Wort Kombi erzielt}\\ q_0& =[\epsilon ]& \\ F& =\{[x]\mid x\in L\}& \end{array}$$ Aus der Definition der Übergangsfunktion $\delta$ gilt jetzt: $$x\in L(M)⟺{\delta }^{\ast }(q_0,x)\in F⟺{\delta }^{\ast }([\epsilon ],x)\in F⟺[x]\in F⟺x\in F$$ und somit haben wir gezeigt, dass dieser Automat existiert und minimal ist!

Wir können ferner jetzt diverse Äquivalenzklassen $[x_1],[x_2],\dots$ generieren, das heißt eine Kombination wird folglich dann äquivalent zu einem bestimmten Wort sein.

[!Info] Nerode-Relation Die Nerode-Relation gehört zu einem Automaten, wobei dieser sehr schlau/gut ist, weil er das obige Problem sehr effizient lösen kann

Minimalautomat |

Die Nerode-Relation lässt eine Klassifizierung von Wörtern in Äquivalenzklassen zu und uns daraus konzeptuell einen Automaten bilden. Dieser Automat wird als Minimalautomat bezeichnet, wenn man ihn umsetzt.

Es folgt daraus ein Korollar:

[!Korollar] Minimalautomat ist eindeutig warum, wie konstruieren wir ihn? #card Sei jetzt$L\in REG$. Dann können wir den obig konstruierten Äquivalenzklassenautomaten $M_0$ als den Automaten mit der kleinsten Anzahl von Zuständen, die $L$ erkennen können, beschreiben.

Dieser Minimalautomat ist bis auf eine Isomorphie eindeutig bestimmt!

Beweis: Auch hier handelt es sich um eine Äquivalenz, weswegen wir beidseitig beweisen können / müssen:

Wir haben obig bereits gesehen, dass für jeden Automaten $M,L=L(M)$ gilt, dass ${\sim }_M$ eine Verfeinerung von ${\sim }_{M_0}$ ist - weil diese Äqui mindestens den Indexvon ${\sim }_L={\sim }_{M_0}$ haben muss. Und daher gilt auch $\mid Q_M|\ge |Q_{M_0}|$. Aber für jedes $M$ mit $\mid Q_M|=|Q_{M_0}\mid$ sind dann auch ${\sim }_M,{\sim }_L$ identisch, weil sie die gleiche Anzahl an Äqui-Klassen haben und weil sie die gleiche Sprache erkennen: $L(M_0)=L(M)$. Somit ist dann $M_0$ der Automat mit der kleinsten Anzahl an Zuständen, der $L$ erkennen kann!

[!Info] Konstruktion Minimalautomat effizient Es ist möglich den Minimalautomaten effizient zu konstruieren: Sei ein DFA $M$ gegeben. Wir suchen dann gezielt nach Paaren von Zuständen $q,q^{\prime }$ sodass $\forall x\in {\Sigma }^{\ast }:{\delta }^{\ast }(q,x)\in F⟺{\delta }^{\ast }(q^{\prime },x)\in f$ und dann können wir sie verschmelzen. Das ganze suchen und verschmelzen kann man in $\mathcal{O}(\mid Q{\mid }^2)$ machen - man muss alle Paare probieren, und die Suche auf Wörter $x:|x\mid \le |Q\mid$ beschränken kann. –> Diese Betrachtung scheint $\mathcal{O}(\mid Q{\mid }^3)$ zu sein, ist es aber nicht xd Ein Beweis liefer etwa Schöning S.38

Entscheidbarkeit auf $REG$

Wir können fur $REG$ Sprachen divers Fragen formulieren, die man entsprechend beantworten kann.

[!Important] Wortproblem was beschreibt es? #card Sei $x\in {\Sigma }^{\ast }$ und $M$ ein DFA. Ist jetzt $x\in L(M)$ Wir können es linear entscheiden –> wir lassen es einfach von $M$ verarbeiten und schauen, ob er akzeptiert oder nicht!

[!Tip] Leerheitsproblem: Sei ein DFA gegeben, ist $L(G)=\varnothing$ ? #card Das Problem können wir entscheiden, denn $L(M)$ ist genau dann leer, wenn es keinen Pfad von $q_0\to q\in F$ gibt

[!Tip] Endlichkeitsproblem: Sei ein DFA gegeben: ist $\mid L(G)\mid <\infty$ ? #card Auch das können wir entscheiden: Sei dafür $n=|Q\mid$. Dann folgt aus dem 112.07_pumping_lemma jetzt: $$\mid L\mid =\infty ⟺\exists w\in L:n\le \mid w\mid <2n$$ Also wir können alle Worte der Länge $n-2n-1$ probieren und prüfen

[!Tip] Schnittproblem: Seien DFAs $M_1,M_2$ gegeben, was ist $L(M_1)\cap L(M_2)=\varnothing$ ? #card Auch das können wir entscheiden: Dafür konstruieren wir den Schnittautomaten und können anschließend schauen, ob der Automat akzeptierende Zustände hat.

[!Tip] Äquivalenzproblem: Seien DFA $M_1,M_2$ ist $L(M_1)=L(M_2)$? #card Auch das können wir in $\mathcal{O}(n^2)$ lösen: Wir bauen dafür den Minimalautomaten von $M_1,M_2$ und prüfen dann auf Isomorphie –> er ist ja eindeutig pro Sprache!