date-created: 2024-04-18 02:58:15 date-modified: 2024-07-10 09:21:28

Reguläre Sprachen | $REG$

anchored to 112.00_anchor_overview requires 112.02_deterministische_automaten

Reguläre Sprachen | REG

reguläre Sprachen sind Teilmengen von der kleenschen Hülle, bei welchen wir einen 112.02_deterministische_automaten finden können, der diese Sprache akzeptieren kann! Also $$L\subset {\Sigma }^{\ast }$$

[!Definition] Ferner heißt dann die Menge aller regulären Sprachen heißt $REG$

(tatsächlich kann man $REG$ auch noch anders definieren, was sie so interessant macht, weil dadurch Abhängigkeiten zwischen den einzelnen Definitionen möglich werden ( also wenn das eine geht, das andere auch, kann man womöglich eine transitive Betrachtung anstellen))

[!Example] leere Sprache $ϵ$ (regulär?)

ist sie regulär? Warum(nicht)? #card

Die Sprache $L=\{ϵ\}$ ist regulär, denn wir können einen DFA bilden, sodass nur das leere Wort akzeptiert wird.

stateDiagram-v2
  [*] --> [q0]
  [q0] --> [u]: 0,1

Wichtig ist, dass alle anderen Eingaben nicht akzeptiert werden dürfen. Also wäre folgender Automat nicht ganz richtig ( zumindest wenn wir totale Übergangsfunktionen voraussetzen):

stateDiagram-v2
[*] --> [q0]

-> denn es wird jedes Wort akzeptiert, weil wir uns von dem Endzustand nicht mehr wegbewegen können / werden

Auch die leere Menge $L=\varnothing$ wäre eine reguläre Sprache, weil wir einen Automat definieren können, der direkt nichts akzeptiert (bzw nie etwas akzeptiert).

[!Important] endliche Sprachen $(\mid L\mid <\infty )$ sind immer regulär.

Warum? #card

Weil wir jetzt einen Automaten bauen können, sodass wir dann für jedes Symbol des Alphabets einen weiteren /nächsten Zustand finden bzw. definieren können.

Diesen Automaten kann man sich als Baum vorstellen, in welchem dann nach in jeder Höhe alle Symbole abgedeckt werden. Man sieht dabei auch, dass sie sehr schnell groß werden würden ( und das macht sie nicht so cool xd)

Wenn wir uns die Regulären Sprachen anschauen, möchten wir schauen, ob wir sie mit mathematischen Operationen ausstatten können und ferner damit bestimmte Operationen möglich sind.

Abgeschlossenheit von $REG$ unter Komplementbildung

Wir möchten einfach annehmen, dass $REG$ abgeschlossen ist, unter Komplementbildung. Also wir behaupten, dass wenn $L$ eine reguläre Sprache über $\Sigma$ ist, dann muss auch $\overline{L}:={\Sigma }^{\ast }\setminus L\in REG$

Also wir können zu irgendeiner Sprache ( $\in L$) einen deterministischen endlichen Automaten betrachten und ferner dann überlegen, wie wir die komplementäre Sprache darstellen können.

Beweis

[!Beweis]

Wir behaupten, dass wenn $L$ eine reguläre Sprache über $\Sigma$ ist, dann muss auch $\overline{L}:={\Sigma }^{\ast }\setminus L\in REG$

Was wäre ein Ansatz das zu zeigen, wie würden wir dabei vorgehen? #card

Die Grundlegende Idee, um das zu zeigen, möchte wir folgend aufstellen:

Wir können einfach die akzeptierenden Zustände und die nicht akzeptierenden Zustände aus unserem Automaten - der sonst die Sprache $L$ akzeptieren kann - setzen, weil dann genau das Komplement der Sprache erkannt werden kann. ( Das geht nur , wenn $\delta$ total ist, sonst könnten da Probleme bzw _zu wenige Zustände entstehen und somit nicht die ganze Sprache erkannt werden.)

Wir folgern aus der Idee jetzt:

Da $L\in REQ$ $\exists$ ein DFA $M=(Q,\Sigma ,\delta ,q_0,F)$ der dann $L$ akzeptieren kann.

-> Wir können daher dann einen neuen Automaten definieren: $\overline{M}=(Q,\Sigma ,\delta ,q_0,\overline{F})$ wobei hier dann also die akzeptierten Zustände $\overline{F}=Q\setminus F$ ist

-> Dabei ist dann $\overline{F}$ eine tatsächliche Teilmenge von $Q$! Denn wir haben ja jetzt einfach alle Zustände genommen, die zuvor nicht akzeptierend waren und sie als “akzeptierend angesetzt”.

Es folgt jetzt hieraus entsprechend:

$$\begin{array}{rl}>\overline{w}\in \overline{L}& ⟺M\text{ akzeptiert }\overline{w}\text{ nicht, da }{\delta }^{\ast }(\overline{w})\notin F\\ >& ⟺\overline{M}\text{ akzeptiert also }\overline{w},\text{ da }{\delta }^{\ast }(\overline{w})\in {\mathbb{Z}}^{\ast }\setminus F=\overline{F}\\ >& \end{array}$$

Abgeschlossenheit der Vereinigung ($\in REG$)

[!Req]

Wir möchten ferner auch noch annehmen, dass $REG$ abgeschlossen ist unter der Vereinigung.

Seien dabei also: $L_1,L_2\in REG$, dann möchten wir herausfinden, ob (bzw. dass!) $L_1\cup L_2\in REG$

Wie würden wir dabei vorgehen, um das zu zeigen? #card

Die Vereinigung deutet hier darauf hin, dass wir einen kombinierten Automaten bauen können / wollen, der sowohl die Wörter aus dem einen und dem anderen Automaten - weil wir können die Sprachen $L_1,L_2$ ja als Automat darstellen - akzeptieren kann / soll.

Wir möchten also zwei Automaten zu einem neuen bauen und dafür für die vorhandenen Sprachen die Automaten definieren:

Gegeben ist also: $L_1,L_2\in REG$ und somit existieren DFAs, die diese beschreiben: $$\begin{array}{r}>M_1=(Q_1,{\Sigma }_1,{\delta }_1,q_0^1,F_1)\\ >M_2=(Q_2,{\Sigma }_2,{\delta }_2,q_0^2,F_2)>\end{array}$$

Um jetzt herauszufinden, welcher der Automaten ein eingegebenes Wort akzeptieren könnte, müssen wir sie irgendwie kombinieren.

Dieses zusammenbasteln wird schnell komplex, weil man von jedem Zustand zu einem anderen aus dem anderen Automaten switchen kann / teils muss, was schwer ist.

-> Das nacheinander Ausführen ist nicht möglich, denn dann müssten wir uns die Eingabe $w$ merken, erst in dem ersten und danach im zweiten Automaten berechnen, weil jeder Automat ja die Eingabe “verspeist”.

(Weiterhin wäre bei so einer Nacheinanderausführung dann der Zustandsraum unendlich), weil es unendlich viele Worte $({\Sigma }_1\cup {\Sigma }_2{)}^{\ast }$ gibt.

Einfacher ist dabei: wir führen beide Automaten parallel aus, um dann entsprechend eine Entscheidung treffen zu können, ob wir jetzt einen akzeptierten Zustand “irgendwo” erreicht haben, oder nicht.

Dafür bauen wir jetzt einen Produktautomaten auf, der genau diese Eigenschaft erfüllen kann. Dieser Automat hat jetzt alle möglichen Zustandspaare der beiden Automaten, also $Q_{new}=Q_1\times Q_2$

[!Tip] Größe der Zustände bei Produktautomat? #card

Größe der Zustände $\mid F_1\mid \cdot |F_2\mid$ wobei $F_1,F_2$ jeweils die akzeptierenden Zustände der Automaten sind.

Wichtig hier ist dabei, bzw das was wir sehen können: -> Wir wollen am Ende nur die akzeptierten Zustände des Automaten betrachten bzw in der Konstruktion dessen nur diese brauchen, wo mindestens ein akzeptierender Zustand dabei ist –> also nur bei der Vereinigung, da es hier die Bildungsvorschrift ist!

Anleitung | Produktautomaten

Wir möchten die Idee jetzt unter Konstruktion des angesprochenen Produktautomaten beweisen.

Gegeben ist also: $L_1,L_2\in REG$ und somit existieren DFAs, die diese beschreiben: $$\begin{array}{r}{M}_1=(Q_1,{\Sigma }_1,{\delta }_1,q_0^1,F_1)\\ M_2=(Q_2,{\Sigma }_2,{\delta }_2,q_0^2,F_2)\end{array}$$

Wir definieren jetzt den Produktautomaten wie folgt: $$\begin{array}{rl}M=& (Q,\Sigma ,\delta ,q_0,F)\\ Q=& Q_1\times Q_2\\ \Sigma =& {\Sigma }_1\cup {\Sigma }_2\\ q_0=& (q_0^1,q_0^2)\\ F=& F_1\times Q_2\cup Q_1\times F_2=\{(q_1,q_2)\mid q_1\in F_1\vee q_2\in F_2\}\\ \delta ((q_1,q_2),a)=& ({\delta }_1(q_1,a),{\delta }_2(q_2,a))\end{array}$$ -> Übergangsfunktion: Wenn hier $a$ in einem der beiden Alphabete ${\Sigma }_1\vee {\Sigma }_2$ nicht definiert ist, dann ersetzen wir es mit “undefined”, also geben einen nicht definierten Zustand als Alternative an, um dennoch beides bilden zu können.

Wir sehen weiter, dass wir sonst die Grundlagen -> also Zustände, Alphabete, Startzustände zusammenlegen, um dann den Automaten zu definieren.

[!Tip] Endzustände $F$ Die Endzustände sind hier so definiert, dass man immer die vorhandenen Endzustände eines Automaten ($F_1,F_2$) mit allen anderen Zuständen des anderen Automaten kreuzt. –> Denn bei der Vereinigung möchten wir alles akzeptieren, was mit dem ersten und auch dem zweiten Automaten akzeptiert wird.

Wir können jetzt diese Definition an die erweiterte Übergangsfunktion knüpfen und müssen beweisen, dass dann die Grundidee - das Anzeigen einer Berechnung für ein Wort $w$ über diese weiterhin funktioniert!

Wir behaupten dafür folgend: $\forall q_1\in Q_1,q_2\in Q_2,w\in {\Sigma }^{\ast }$ gilt dann jetzt: $${\delta }^{\ast }((q_1,q_2),w)=({\delta }_1^{\ast }(q_1,w),{\delta }_2^{\ast }(q_2,w))$$ -> also wir können diese Umsetzung aufsplitten, sodass der Prozess für beide gleichzeitig durchgeführt wird und am Ende die Tupel der akzeptierten Zustände erreicht werden kann.

Auch das können wir wieder unter Anwendung der Induktion beweisen ( wie es bei der “normalen” Übergangsfunktion funktionierte).

$$\begin{array}{rl}IA& =n=0,w=ϵ:\\ & ={\delta }^{\ast }((q_1,q_2),ϵ)=({\delta }_1(q_1,ϵ),{\delta }_2(q_2,ϵ))\\ & =(q_1,q_2){=}^{\text{Behauptung}({\delta }_1^{\ast }(q_1,ϵ),{\delta }_2^{\ast }(w_2,ϵ))}\square \\ IS& =n\to n+1L\text{ Sei }{w}^{\prime }\text{ ein Wort der La¨nge }n\text{ und weiterhin ein neuer Buchstabe}\sigma \in \Sigma \\ & \text{ Wir betrachten dann jetzt folgend: }w=w^{\prime }\sigma :\\ & ={\delta }^{\ast }((q_1,q_2),w){=}^{\text{ Def erweiterte U¨F}}\delta ({\delta }^{\ast }((q_1,q_2),w^{\prime }),\sigma )\text{ wir haben das Suffix verarbeitet!}\\ & =\delta (({\delta }_1^{\ast }(q_1,w^{\prime }),{\delta }_2^{\ast }(q_2,w^{\prime })),\sigma )\\ & {=}^{\text{def U¨F}}({\delta }_1({\delta }^{{\ast }_1}(q_1,w^{\prime }),\sigma ),{\delta }_2({\delta }_2^{\ast }(q_2,w^{\prime }),\sigma ))\\ & =({\delta }_1^{\ast }(q_1,w),{\delta }_2^{\ast }(q_2,w))\\ & =\text{ was wir ja behauptet haben, also passt!}\end{array}$$

Damit hat man die Umformung, muss aber noch entsprechend anpassen!

-> Wir haben definiert, dass $F$ immer dann ein Wort $w$ akzeptiert, genau wenn $M_1,\vee M_2$ es akzeptieren.

o.B.d.A gilt dann, wenn $w\in {\Sigma }^{\ast },M_1(w)=true$, folgendes: $${\delta }^{\ast }(w)=({\delta }_1^{\ast }(q_1,w),{\delta }^{{\ast }_2(q_2,w))}\in F$$ (Also hier ) beispielsweise ein akzeptierender Zustand im ersten Teil, also ${\delta }_1^{\ast }(q_1,w)$ getroffen, weil $M_1$ dieses Wort akzeptiert. (Selbiges gilt dann auch für $M_2$)

Wir möchten ferner noch ein Beispiel dazu betrachten: Seien dafür zwei Automaten gegeben:

stateDiagram-v2
[*] --> s1
s1 --> [s2]:0,1
[s2] --> s1:0,1
[**] --> q1
q1 --> [q3]: 0
q1 --> q2:1
q2 --> q1:0
q2 --> [q3]:1
[q3] --> [q3]:0,1

Wir wissen, dass wir hier jetzt beim neuen Automaten $2\cdot 3=6$ Zustände haben können, die wir betrachten müssten. Weiter sehen wir aber auch, dass es Zustände geben wird, wo beide nicht akzeptieren ( und wir somit die anderen weglassen könnten)

Das macht man sich am einfachsten via Tabelle klar:

stateDiagram-v2
[*] --> (s1,q1)
(s1,q1) --> [(s2,q3)]:0
(s1,q1) --> [(s2,q2)]:1
[(s2,q2)] --> (s1,q2):0
[(s2,q2)] --> [(s1,q3)]:1
[(s2,q3)] --> [(s1,q3)]:0,1
[(s1,q3)] --> [(s2,q3)]:0,1

Abgeschlossenheit des Schnitts und Differenz ($\in REG$)

Wir behaupten jetzt: Seien $L_1,L_2\in REG$ Dann sind auch $L_1\cap L$ und ferner auch $L_1\setminus L_2$

Beweisidee:

Wir könnten ähnlich, wie bei [Abgeschlossenheit der Vereinigung ($inREG$)](#Abgeschlossenheit%20der%20Vereinigung%20()) die akzeptierenden Zustände $F$ anpassen und dadurch die Idee neu konstruieren. (Wenn man nur $F$ verändert, muss man die Induktion nicht nochmal beweisen, da das unabhängig davon agiert / funktioniert)

Alternativ könnte man das auch über Mengenlehre betrachten und lösen:

Möglicher Beweis (Mengenlehre)

Mittels Umformungen (boolesche Umformungen) gilt: $L_1\cap L_2=\overline{\overline{L_1}\cup \overline{L_2}}$ ( und weil wir die Vereinigung schon gezeigt haben!) ist somit auch $L_1\cap L_2$ regulär!

Alternativ können wir wieder einen Produktautomaten konstruieren, der dann $L_1\cap L_2$ akzeptiert. Hierbei unterscheidet sich zum Beweis nicht viel, bis auf die akzeptierten Zustände: $$F=F_1\times F_2=\{(q_1,q_2)\mid q_1\in F_1\wedge q_2\in F_2\}$$ -> es müssen also beide Automaten akzeptieren, damit der neue Zustand des Tupels akzeptiert!