cards-deck: university::theo_complexity

Language, finite state machines

this is part of [[112.00_anchor_overview]] previous chapter [[112.01_Sprachen]]

what are finite state machines useful for ? #card With those we can generalize the data flow and execution progress for a given program :: ^1686580398325 What we can do with those : -

Eingaben verarbeiten –> Wörter und Sprachen
etwas berechnen –> Übergangsfunktion
etwas speichern –> Zustände
Ausgaben produzieren ^1686580398336

Alphabets | non-empty sets filled with symbols :

Sei $\sum$ eine nicht-leere, endliche Menge . Wir bezeichnen sie nun als ein Alphabet. wie beschreiben wir die Elemente der Menge? #card Die Elemente der Mengen werden dann in diesem Kontext mit “Symbolen” – auch Buchstaben – bezeichnet.

Ein Wort $w$ ist eine endliche Folge von :: Buchstaben des Alphabets. ^1686580398342

Definition der Länge eines Wortes :

wie notieren wir die Eigenschaft der Länge eines Wortes? #card Die Anzahl der Buchstaben heißt die Länge des Wortes $w$ und wir notieren dies mit $∣ w ∣$ Gezielte Wörter $w$ können auch als Array-like Konkatenationen definiert werden $w = w_{1}, w_{2} \dots$ Ein leeres Wort $ϵ$ ist ein besonderes, leeres Wort. also $∣ ϵ ∣ = 0$ ^1686580398347

Kleene’sche Hülle :

Die Menge aller Wörter der Länge n über $Σ$ bezeichnen wir mit :: $Σ^{n}$ , wobei dann n angibt, wie lang das Wort ist. Also wir haben eine Menge definiert, die alle konstruierbaren Wörter des Alphabetes mit einer gewissen Länge definiert. ^1686580398351

Definition der Kleene’schen Hülle: in welchem Kontext können wir von einer kleene’schen Hülle sprechen #card Die Menge aller Wörter über $Σ$ bezeichne wir mit $Σ^{*} := ⋃_{n = 0}^{\infty} Σ^{n}$ Dabei ist wichtig, dass diese Menge abzählbar unendlich ist. Also sie deckt ein unendliches Feld an Wöýtern ab. ^1686580398355

Sprache :

Wir können eine Sprache definieren, indem wir eine Menge erstellen, die einen gewissen Scope von Wörtern beinhaltet. wie würden wir dies formal aufschreiben? Wann sprechen wir von endlich/unendlich? #card $Σ^{+} := ⋃_{n = 1}^{\infty} Σ^{n}$ –> Die Sprache beinhaltet demnach Wörter, welche verschiedener Längen entspringen kann Für diese gilt, dass sie endlich ist und ein Submenge der Kleen’schen Hülle, denn sie beinhaltet alle Elemente, die auch in der Sprache enthalten sind. ^1686580398359

Konkatenation von Sprachen :

Seien $L_{1}, L_{2}$ Sprachen und $w, u \in L_{1}, L_{2}$ , dann ist die Konkatenation : wie definieren wir die Konkatenationen $\circ$ und $L^{*}$ ? #card $L_{1} \circ L_{2} := {u w ∣ u \in L_{1}, w \in L_{2}}$ –> Die Kleen’sche Hülle einer Sprache L ist dann definiert als : $L^{*} := {x_{1},^{'} l d o t s, x_{n} ∣ x_{i} \in L, k \in N_{0}^{'}}$ Sofern wir ein Wort k-mal an sich selber hängen, schreiben wir diese Knüpfung : $w^{k} = w \dots w$ –> das k-mal durchgeführt. ^1686580398363

Betrachtung einer Konkatenation als Gruppe #card Die Operation der Konkatenation kann auch als eine Gruppe betrachtet werden, obwohl diese nicht wirklich einer entspricht. wir können feststellen, dass die Operation assoziativ ist. Jedoch nicht kommutativ, weil die Konkatenation ein anderes Wort erzeugt und somit nicht gleich ist, wenn wir die Reihenfolge der Konkatenation ändern. ^1686580398366

Weiterhin gibt es mit dem leeren Wort $ϵ$ ein neutrales Element.

Teilwörter, Präfixe, Suffixe :

Ein Wort $x$ heißt Teilwort eines Wortes $y$ , falls :: es Wörter $u, v$ gibt, sodass $y = uxv$ . Das heißt, unser gesuchtes Wort kann sich innerhalb einer Wortgruppe befinden. ^1686580398371

Wenn dabei $u = ϵ$ , dann heißt X Präfix von y –> es steht am Anfang des Wortes und zuvor tritt kein Wort auf.
Falls $v = ϵ$ , dann heißt X Suffix von y –> es steht am Ende des verbundenen Wortes.

01 ist ein Teilwort von 00111.
10 ist ein Präfix von 10111110001
011 ist ein Suffix von 000111010101011

Finite State Machines :

stateDiagram-v2
[*] --> idle : we start our machine
idle  --> action : idle until input 
action --> idle : done, waiting for next input 
action --> termination : done working, shutting down

definition of a deterministic automata :

Ein endlicher, deterministischer Automat wird beschrieben durch 5-Tupel $(Q, Σ, δ, q_{0}, F)$ wobei : wofür stehen alle 5 Elemente des Tupels? #card

$Q$ ist eine endliche Menge, die die Zustände beschreibt –> Es ist ein endlicher Automat,, weil die Menge der Zustände endlich ist!
$Σ$ ist eine endliche Menge, das Alphabet –> endliche Menge von Buchstaben / Wörtern
$δ$ : $Q \times Σ ⟶ Q$ die Übergangsfunktion –> beschreibt, wann wir von einem Zustand zum nächsten wechseln.
$q_{0} \in Q$ der Startzustand
$F \subset Q$ die Menge der akzeptierenden Zustände. –> Alle möglichen Zustände, die akzeptiert werden, d.h. welche verarbeitet und zu einem Ergebnis führen ![[Pasted image 20230425122200.png]] ^1686580398375

current state	new input 0	new input 1
q1	q1	q2
q2	q3	q2
q3	q2	q2

Partielle vs. totale Übergangsfunktionen

Wenn wir von partiellen Übergangsfunktionen sprechen, was ist dann gemeint? #card Manchmal werden Übergangsfunktionen nur partiell definiert, also es sind nicht alle möglichen Übergange in dem Automat möglich. unsere Vorlesung wird alle Übergänge definieren ![[Pasted image 20230425122429.png]] ^1686580398379

Berechnung eines Automaten :

Sei eine Folge $s_{0}, \dots, s_{n} \in Q$ von Zuständen. Dann heißt sie Berechnung des Automaten $M = (Q, Σ, δ, q_{0}, F)$ auf einem gegebenen Wort $w = w_{1}, \dots, w_{n}$ , falls gilt : #card $s_{0} = q_{0}$ –> der Startzustand ist gleich der ersten Folge aus unserer Menge Q, die den Input definiert. $\forall i = 0, \dots, n - 1; s_{1 + i} = δ (s_{i}, w_{i + 1})$ Also eine gültige Folge von Zuständen, die man durch Abarbeiten des Wortes W erreicht. Man nennt sie dann eine gültige Berechnung. ^1686580398383

Beispiel :

![[Pasted image 20230425122839.png]] Nenne einige Berechnungen dieses DEA, Betrachte die Eingabe 001 #card sei das Wort = 001, dann haben wir die Zustandsfolge: $q_{1} ⟶^{0} q_{1} ⟶^{0} q_{1} ⟶^{1} q_{2}$ Weiterhin gilt für das Wort w=010: $q_{1} ⟶ q_{1} ⟶ q_{2} ⟶ q_{3}$ ^1686580398387

Akzeptiere Sprache(n) :

Wir können für viele Wörter berechnen, ob sie akzeptiert und gültig sind, jedoch kann man diese Zustände von Wörtern auch in einer akzeptierten Sprache zusammenfassen. Dafür betrachten wir : was müssen wir für einzelne Worte betrachten? Was ist dann weiterführend die akzeptierte Sprache? #card Eine Berechnung akzeptiert das Wort $w$ , falls die Berechnung in einem akzeptierten Zustand endet. Die von einem endlichen Automaten M akzeptierten bzw (erkannte) Sprache L(M) ist die Menge der Wörter, die von M akzeptiert werden: Es folgt $L (M) := {w \in Σ^{*} ∣ M ak ze pt i er tw}$

Dabei kann es vorkommen, dass in der Berechnung ein Akzeptierter Zustand vor Beendigung der Eingabe getroffen wird, uns interessiert hier nur der Endzustand und ob er Akzeptiert wird ^1686580398390

Beispiel Folie 37

Erweiterte Übergangsfunktion :

Mit der Übergangsfunktion können wir Schritt für Schritt angeben, wie ein Automat eine Eingabe - Wort - verarbeitet. Wenn wir beispielsweise 1,0,0,0,0,0 verarbeiten, kann es von Nutzen sein, diesen Übergang in einer kürzeren, kompakten Form aufzuschreiben. Dafür definieren wir die erweiterte Übgergangsfunktion, welche induktiv n-viele Schritte zusammenfassen kann. wie wird sie nun beschrieben? #card Sei $δ : Q \times Σ ⟶ Q$ eine Überganfsfunktion eines Automaten. Wir definieren die erweiterte Übergangsfunktion $δ^{*} L Q \times Σ^{*} ⟶ Q$ und beschreiben sie, wie folgt:

$δ^{*} (q, ϵ) = q \forall q \in Q$
Für $w \in Σ^{*}; a \in Σ$ setzen wir dann: $δ^{*} (q, w a) = δ (δ^{*} (q, w) a)$ dabei ist $δ^{*} (q, w)$ der Zustand nachdem wir $w$ gelesen haben. und $. a$ ist der Buchstaba $a$ den wir anschließend lesen ^1686580398394

Reguläre Sprachen :

Eine Sprache $L \subset Σ^{*}$ heißt reguläre Sprache, wenn :: es einen endlichen Automaten M gibt, der diese Sprache akzeptiert(en kann). Eine Sprache ist also regulär, wenn wir einen Automaten konstruieren können, der diese Sprache verarbeiten und mit akzeptierten Zuständen verarbeiten kann. ^1686580398398

Die Menge aller regulären Sprachen bezeichnen wir anschließend als :: REG ^1686580398401

Gibt es Sprachen, die nicht akzeptiert werden können? Kann man diese dann geschickt beschreiben?

Erste Beobachtung zu Sprachen :

Endliche Sprachen sind immer regulär. warum ist das so, wie kann man das beweisen? #card

Beweisen kann man es, indem jeder Zustand als Endzustand definiert wird. Weiterhin muss die Übergangsfunktion vollständig definiert sein, also jeder Zustand kann auf einen anderen Zustand zeigen –> somit ist jede Kombination von Buchstaben möglich und wird im Universum der Sprache akzeptiert. ^1686580398405

Betrachtung diverser Eigenschaften von Regulären Sprachen:

Sei $L$ eine reguläre Sprache über $Σ$ . Dann ist auch $\overset{ˉ}{L} := Σ^{*} ∖ L$ eine reguläre Sprache. was haben wir mit diesem Ausdruck jetzt beschrieben? Warum ist diese Menge immernoch regulär? #card Das heißt, dass wir mathematisch betrachtet zu der Menge $L \in Σ$ eine Komplementmenge bilden, welche eben alle Wörter in der kleene’schen Hülle $Σ^{*}$ beinhaltet, außer die, die sich in $L$ befinden. Veranschaulicht wäre das demnach: ![[Pasted image 20230426205355.png]] ^1686580398409

Beweis Idee

was wäre ein Ansatz um die obige Aussage zu beweisen? #card Man könnte das Ganze eventuell damit beweisen, indem man die akzeptierten Zustände mit den nicht-akzeptierten Zuständen des Automaten vertauscht. -> Wie zuvor angesprochen, kann es schwierig werden, wenn die Übergangsfunktion nur partiell definiert wird, also nicht alle Übergänge vermerkt und somit nutzbar sind, aber sonst ist es machbar. ^1686580398413

Formeller Beweis :

Ist $L$ regulär, dann impliziert das $⟹ \exists M = (Q, Σ, δ, q_{0}, F)$ , welcher L akzeptiert. wie können wir das jetzt weiter beweisen, mit diesem Anfang? #card M ist hierbei ein Automat, was man an dem 5-Tupel erkennen kann. Nun erzeugt man den Komplementautomate: $\overset{ˉ}{M} = (Q, Σ, δ, q_{0}, \overset{ˉ}{F})$ wobei $\overset{ˉ}{F} := Q ∖ F$ ^1686580398418

Mit dieser Betrachtung gilt dann : $w \in \overset{ˉ}{L} ⟺ M$ akzeptiert $w$ nicht. Weiterhin $⟺ \overset{ˉ}{M}$ akzeptiert w. Somit ist gezeigt, dass das Komplement sich nicht mit dem Automaten bedienen lässt und umgekehrt auch der Komplementautomat nicht mit den Element von $L$ interagieren kann, um einen akzeptierten Zustand zu erhalten.

Satz - Abgeschlossenheit Vereinigung von Sprachen :

Die Menge der regulären Sprachen ist abgeschlossen bezüglich der Vereinigung: Sei dafür $L_{1}, L_{2} \in REG ⟹ L_{1} \cup L_{2} \in REG$ warum folgt das? Wie können wir das eventuell beweisen? #card

Beweis Idee

Das ist logisch, da $L_{1}, L_{2} \in REG$ , welche die Menge aller regulären Sprachen definiert, auch die Vereinigung zweier regulärer Sprachen beinhalten muss. Denn unter der Vereinigung lässt sich ein Automat konstruieren, welcher die Vereinigung der beiden Automaten der regulären Sprache $L_{1}, L_{2}$ verarbeiten und in akzeptierten Zuständen resultieren kann. ^1686580398423

Wir haben resultiert, dass eine Vereinigung zweier Sprachen auch in der Menge aller Regulären Sprachen (REG) beinhaltet ist, und somit die Abgeschlossenheit folgen muss. Wie könenn wir das jetzt formal beweisen? #card Um das zu beweisen, könnte man entweder schauen, dass beide Automaten serielle - also nacheinander - implementiert und genutzt werden, man könnte aber auch eine parallele Verarbeitung realisieren. Tatsächlich kann man beide Automaten nicht seriell laufen lassen, wenn wir ein Wort $w$ als Eingabe erhalten und in der Vereinigung betrachten möchten. Es kommt zu Problemen, wenn das Wort vom zweiten Automaten akzeptiert wird, jedoch der erste Automat die Eingabe niemals akzeptieren wird und somit niemals eine Antwort entstehen kann. Wir müssen sie somit parallel laufen lassen, damit einer der beiden Automaten einen akzeptierten Zustand annimmt, und diese danach terminieren. Also, dass jeder Zustand als (Tupel) definiert wird. Daraus entsteht ein Produktautomat Problem damit :: Skaliert sehr stark, da man immer die Produkte der beiden Automaten als Zustände darstellt –> 10 x 10 = 100 Zustände für Produktautomat ^1686580398428 ^1686580398433

Beispiel :

Sei $M_{1}$

stateDiagram-v2 
classDef acceptedState fill:#fff,color:black

[*]-->S1
S1-->S2: 0,1
S2 -->S1: 0,1
S2:::acceptedState

und $M_{2}$

stateDiagram-v2
classDef acceptedState fill:#fff,color:black
[*]-->q1
q1-->q3:0
q3-->q3: 0,1
q2-->q1:0
q2-->q3:1
q1-->q2:1
q3:::acceptedState

und die Vereinigung beider Automaten $M_{1} \times M_{2}$ wäre somit:

stateDiagram-v2 

classDef acceptedState fill:#fff,color:black

state "s1,q1" as s0
state "s2,q2" as s1
state "s2,q3" as s2
state "s1,q3" as s3
s3:::acceptedState
s2:::acceptedState
s1:::acceptedState

[*]-->s0
s0-->s1:1
s1-->s0:0

s0-->s2:0

s2-->s3:0,1
s3-->s2:0,1

s1-->s3:1

und wir können damit diverse Wörter eingeben und in Endzuständen resultieren. $0 \in L_{1} \cup L_{2}$ $01 \in L_{1} \cup L_{2}$ $10 \neq \in L_{1} \cup L_{2}$ , denn wenn wir den Initialzustand betrachten, dann ist weiterführend eine 1 als Eingabe valide, jedoch anschließend keine 0 mehr möglich, somit erhalten wir keinen akzeptierten Zustand.

Beweis :

Man kann diese Struktur des Produktautomaten beweisen, indem man diesen mit Induktion konstruiert. Wir definieren den Produktautomaten $M := M_{1} \times M_{2}$ wie folgt: Sei $M = (Q, Σ, Δ, s, F)$ und definieren wir alle Elemente des Tupels entsprechend: $Q = Q_{1} \times Q_{2}$ $Σ = Σ_{1} \cup Σ_{2}$ $s = (s_{1}, s_{2})$ –> Der Startzustand ist in dem Falle das Tupel beider Startzustände, der Sprachen! $F = {(f_{1}, f_{2}) ∣ f_{1} \in F_{1} \lor f_{2} \in F_{2}}$ –> Also die Menge der akzeptierten Zustände, welche entweder in der Menge der ersten oder zweiten ist ! Wichtig bzw relevant wird die Übergangsfunktion:: ^1686580398438 $Δ : Q \times Σ ⟶ Q, Δ ((r_{1}, r_{2}), a) = (δ_{1} (r_{1}, a), δ_{2} (r_{2}, a))$ Hierbei ist $r_{1} \in Q_{1}; r_{2} \in Q_{2}, a \in Σ$

Unter der Prämisse der Vorbetrachtung und der Neudefinition, können wir eine neue, erweiterte Funktion definieren. Es gilt dann $\forall q_{1} \in Q_{1}, q_{2} \in Q_{2}, w \in Σ^{*}$ : eine neue Übergangsfunktion : $Δ^{*} ((q_{1}, q_{2}), w)$ welche gleich der alten Funktion(erweitert) ist. $⟺ (δ_{1}^{*} (q_{1}, w), δ_{2}^{*} (q_{2}, w))$

Den Beweis kann man nun mit der Induktion nach $n := ∣ w ∣$ Also der Länge des Wortes bestimmen.

Dafür sei der Induktionsanfang: IA: $∣ w ∣ = 0$ Dann ist w= $ϵ$ –> das leere Wort und nach Definition der erweiterten Übergangsfunktion gilt mit dieser: $Δ^{*} ((q_{1}, q_{2}), ϵ) = (q_{1}, q_{2})$ und $δ_{1}^{*} (q_{1}, w) = q_{1}; δ_{1}^{*} (q_{2}, w) = q_{2}$ –> entspricht in etwa einer Identitätsabbildung.

Es folg der Induktionsschritt : IS: $n ⟶ n + 1$ Sei $w^{^{'}}$ ein Wort der Länge $n, ω \in Σ$ ein Buchstabe. Wir betrachten jetzt das Wort : $w := w^{^{'}} ω$ .

$Δ^{*} ((q_{1}, q_{2}), w) = Δ (Δ^{*} ((q_{1}, q_{2}), w^{^{'}}), ω)$ —> entspricht der Definitino von der Übergangsfunktion und $w$ WIr beziehen nun die Induktionsannahme mit ein: $Δ ((δ^{*} (q_{1}^{*}, w^{^{'}}), δ_{2}^{*} (q_{2}, w^{^{'}})), ω)$ –> ferner können wir das übrig gebliebende $Δ$ nochmals in die Definition umwandeln, und erhalten: $⟺ (δ_{1} (δ_{1}^{*} (q_{1}, w^{*}), ω), δ_{2} (δ_{2}^{*} (q_{2}, w^{^{'}}, ω))$ –> was sich durch kürzen relativiert und den Ausgangszustand ergibt: $⟺ (δ_{1}^{*} (q_{1}, w), δ_{2}^{*} (q_{2}, w))$ Es ist weiterhin noch eine weitere Annahme relevant: Wir nehmen an: Der Produktautomat akzeptiert $L_{1} \cup L_{2}$ Nach der gegebenen Funktion $F$ akzeptiert $M$ ein Wort $w$ , wenn $M_{1}$ oder $M_{2}$ das entsprechende Wort akzeptieren, es also in einem der beiden enthalten ist. In der Induktion haben wir gesehen, dass die Berechnung von $M$ sich auf die Komponenten runterbrechen lässt. Daraus folgt dann also die Grundannahme des Satzes!

Satz : Abgeschlossenheit Schnitt/Differenz von Sprachen:

Zuvor haben wir die Vereinigung betrachtet, dieses mal schauen wir uns die Schnittmenge und DIfferenz an.

Seien $L_{1}, L_{2}$ zwei reguläre Sprachen. Dann sind auch $L_{1} \cap L_{2}$ und $L_{1} ∖ L_{2}$ reguläre Sprachen. warum folgtdas? Was wäre eine Beweisidee? #card Informelle Beweisideen: Ein Beweis dafür kann unter Umständen mit der Betrachtung gestellt werden, dass man eine Komplementmenge bilden kann und die für beide Mengen darstellt und so die gewollten Zustände definiert. Weiterhin besteht die Möglichkeit die selbige Induktion, wie obig charakterisiert, aufzubauen, jedoch mit einer Modifikation der akzeptierten Zustände, wie folgt: $L_{1} \cap L_{2} ⟶ F := {(q_{1}, q_{2}) ∣ q_{1} \in F_{1} \land q_{2} \in F_{2}}$ Also der Endzustand muss sich zwingend in beiden Automaten befinden, ferner muss der Endzustand eine Konkatenation von zwei akzeptierten Endzuständen aus den anderen Automaten sein. DIe Komplementmenge hilft uns, um die Differenz zu beweisen: $L_{1} ∖ L_{2} = L_{1} \cap \neg L_{2}$
![[Pasted image 20230427000058.png]] ^1686580398443

scattered-lenity