cards-deck: 100-199_university::111-120_theoretic_cs::112_complexity_theory

Deterministische endliche Automaten (DFA)

anchored to 112.00_anchor_overview proceeds from 112.01_Sprachen and leads to 112.02_deterministische_automaten

Overview

Viele Systeme im Alltag haben die Grundidee, dass sie zwischen diversen Zuständen traversieren, etwa weil sie erst einen bestimmten Zustand brauchen, um dann von diesem zu einem anderen übergehen zu können. Einfach Beispiele dafür wären etwa:

Waschmaschinen, die zwischen “warten”, spülen, heizen, und öffnen bzw. Ende traversieren -> In diesem Beispiel ist ersichtlich, dass diverse Zustände von anderen abhängig sind bzw nur als Folgerungen von einem zum anderen Zustand springen können.

Konstruieren möchten wir diese Idee dieses Konzept unter Anwendung von Automaten.

Definition

Wir möchten den Automaten als Konstruktion eines Tupels erzeugen / darstellen.

[!Definition] deterministischer endlicher Automat Wir beschreiben einen DFA $M$ unter Anwendung eines $5 -$ Tupels folgend: $M := (Q, Σ, δ, q_{0}, F)$

Was bedeuten die einzelnen Symbole des Tupels? #card

Bedeutungen dieser einzelnen Werte:

$Q$ beschreibt die endliche Menge deren Elemente Zustände genannt werden –> also wir fassen alle Zustände, die unser Automat haben kann zusammen

$Σ$ beschriebt die Menge des Alphabets –> dabei wird die Eingabe aus den Symbolen, die das Alphabet definiert, bestehen –> Wort ( $w = x_{1}, \dots, x_{i} ∣ x_{i} \in Σ$ )

$δ$ beschreibt dabei die ganzen Übergangsfunktionen, also $Q x Σ ⟹ Q$ –> die Übergangsfunktion gibt an nach welcher Bedingung wir dann zu einem anderen Zustand springen können (also die Pfeile )

$q_{0}$ beschriebt den Startzustand bei welchem wir starten und dann von diesem zu anderen Zuständen springen können.

$F \subseteq Q$ beschreibt dann die Menge von akzeptierenden Zuständen –> also da, wo unser Automat eine Eingabe dann akzeptieren kann! ^1720638270057

[!Tip] totale Übergangsfunktion Wenn für jeden Zustand und jedes Symbol ( aus dem Alphabet) ein Übergang existiert, dann weist ein DFA folgend eine totale Übergangsfunktion auf.

Was gilt damit dann? #card

Ferner gilt also: $\exists δ (q, γ) \forall (q, γ) \in Q x Σ$

[!Warning] partielle Übergangsfunktionen sind demnach diese, die nicht für alle Symbole eine Übergangsfunktion definiert haben. Also wenn man einen Zustandsautomat aufschreibt, der nicht jede Kombination von Zustand und Symbole (aus dem Alphabet) abdeckt und so “Lücken bestehen”. ^1720638270092

[!Tip] Überführung einer partiellen Übergangsfunkion

Wir können eine partielle Übergangsfunktion relativ einfach in eine totale Übergangsfunktion überführen, indem wir folgend vorgehen:

Welche Schritte müssen wir durchlaufen, um das umzusetzen? #card

Für die Symbole, die noch nicht abgedeckt werden, definieren wir einen Zustand $u$ = undefined, sodass dann für die Kombinationen (also (Zustand,Symbol) ) ein Zustand existiert, wohin geleitet wird.

Also einfach gesagt haben wir einfach einen neuen Zustand - der dann den DFA “in sich fängt und nicht mehr herauslässt” - (ein schwarzes Loch!), was alle nicht explizit genannten Übergange in sich beschreibt ^1720638270096

Berechnung eines Automaten

Ferner möchten wir definieren, wie ein Automat ausgewertet und somit dann evaluiert werden kann, ob das Wort akzeptiert wird oder nicht.

Wir wollen entsprechend definieren:

[!Definition] Berechnung (eines Automaten)

Wir nennen jetzt eine Folge $s_{0}, \dots, s_{n} \in Q$ von Zuständen die Berechnung des Automaten $M := (Q, Σ, δ, q_{0}, F)$ auf dem Wort $w = w_{1}, w_{2}, \dots, w_{n}$ wenn gilt:

Welche Zwei Aspekte müssen hierbei gelten? #card

$s_{0} = q_{0}$ - also die Auswertung kann am Startzustand des Automaten starten und dann von da weiter “die Zuständen abhängig von der Übergangsfunktion berechnen”

$\forall i = 0, 1, \dots, n - 1$ gilt dann für die Elemente der Folge: $s_{i + 1} = δ (s_{i}, w_{i + 1})$ ( Also der nächste Zustand $s_{i + 1}$ ergibt sich aus der Anwendung der Übergangsfunktion mit den derzeitigen Zustand und dem nachfolgenden Symbol aus dem Wort) ^1720638270099

Betrachten wir folgendes Beispiel:

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

Wir können daraus folgende Information über den Automaten entnehmen: $Q = {q_{0}, q_{1}, q_{2}}$ , $Σ = {0, 1}$ , $F = {q_{1}}$ Wir können diesen Sachverhalt auch als Tabelle darstellen:

$δ$	0	1
$q_{0}$	$q_{0}$	$q_{1}$
$q_{1}$	$q_{2}$	$q_{1}$
$q_{2}$	$q_{1}$	$q_{1}$
-> lesen können wir die Tabelle so, dass im linken Zustand unter Anwendung der Übergangsfunktion und der Eingabe (Spalten-köpfe, also 0 oder 1) dann folgender nächster Zustand folgen wird.
Also wenn wir etwa im Zustand $q_{0}$ sind, anschließend als Eingabe $0$ haben, dann wird $δ (q_{0}, 0) = q_{0}$ resultieren, wir sind also im entsprechenden Zustand gelandet.

Ferner kann man auch ein Wort dadurch “berechnen”: $w = 010$ wäre jetzt hier: $q_{0} \to^{0} q_{0} \to^{1} q_{1} \to^{0} q_{2}$ ( was kein akzeptierter Zustand ist!) $w = 001$ wäre: $q_{0} \to^{0} q_{0} \to^{0} q_{0} \to^{1} q_{1}$

erweiterte Übergangsfunktion:

[!Definition] erweiterte Übergagnsfunktion Sei hier wieder $δ : Q x Σ \to Q$ eine Übergangsfunktion. Wir definieren die erweiterte Übergangsfunktion folgend:

Wie definieren wir sie? Wozu brauchen wir dieses Konstrukt, was wird uns damit ermöglicht? #card

$δ^{*} : Q x Σ^{*} \to Q$ Damit folgt dann beispielsweise für das leere Wort ( was ja $\subseteq Σ^{*}$ ist) folgend: $δ^{*} (q, ϵ) := q, \forall q \in Q$ Wir können damit einfach immer vom Anfang, wo noch kein Wort anliegt ( quasi das leere Wort der einzige “Input” ist) schrittweise das gegebene / neue Wort durchlaufen ( also Buchstabe für Buchstabe bzw Symbol). Also ferner: $\forall w \in Σ^{*}, a \in Σ, q \in Q$ können wir dann folgend setzen: $δ^{*} (q, w a) := δ (δ^{*} (q, w), a)$

(Wir expandieren also die “Auswertung” indem wir immer den zuvor herrschenden Zustand ( welcher ja auch aus der Übergangsfunktion berechnet wird) einsetzen und quasi “rekursiv” agieren).

Hierbei ist etwa $δ^{*} (q, w)$ der Zustand, der nach der Eingabe von $w$ ( wir haben ja $w a$ konstruiert, was zwei Wörter einfach konkateniert hat!) eintritt ( und dann die Eingabe von $a$ folgen wird!)

Wenn jetzt $δ^{*} (q, w)$ nicht definiert ist, dann setzen wir es auf undefined ^1720638270103

Mit dieser Definition können wir jetzt die Berechnung eines Automaten $M$ kompakter darstellen. Also für ein Wort $w$ nicht mehr nach und nach die Zustände aufschreiben, sondern mit $δ^{*} (w)$ aufschreiben ( was sich dann in der obigen Definition selbstständig rekursiv aufsplittet und einzelne Berechnungsschritte beschreibt!)

akzeptierte Worte und Sprachen

Hier wird jetzt eine erste Abhängigkeit zu der Idee von 112.03_reguläre_sprachen gesetzt, weil man diese benötigt, um sie zu beweisen ( Die beiden Dinge sind stark miteinander verbunden, in der Betrachtung, dass durch die eine Struktur das andere begründet bzw bewiesen werden kann).

Wir sagen, dass eine Berechnung ein Wort $w$ akzeptiert, falls $δ^{*} (q_{0}, w) \in F$ also falls die Berechnung auf das Wort $w$ anschließend in einem akzeptierten Zustand enden wird / endet.

Dadurch können wir also eine Menge von Wörtern konstruieren, die unser Automat dann akzeptieren kann/muss. Ferner bildet sich daraus eine Bildungsvorschrift und somit auch eine akzeptierte Sprache!

[!Definition] akzeptierte Sprache eines DFA

Die von einem DFA $M = (Q, Σ, δ, q_{0}, F)$ akzeptierte Sprache $L$ - geschrieben: $L (M)$ - ist die Menge der Wörter, die von $M$ akzeptiert werden.

Wie definieren wir sie demnach? #card

Ferner definieren wir sie dann mit: $L (M) := {w \in Σ^{*}} ∣ M akzeptiert w = {w \in Σ^{*} ∣ δ^{*} (w) \in F}$

Aus der Menge von allen Wörtern, der kleenschen Hülle nehmen wir jetzt die Teilmenge, die “existiert” und zusätzlich vom Automaten erkannt wird. Das bildet dann eine Menge von Wörtern, die eine Sprache bilden kann / wird. ^1720638270106

[!Important] in akzeptiert $\neq =$ wird akzeptiert

Sofern eine Berechnung vor Abschluss in den akzeptierenden Zustand ein- und wieder austreten wird, muss sie nicht zwingend akzeptiert werden.

Warum ? (relativ einfach) #card

Es ist wichtig dass der Zustand nach dem letzten Buchstaben akzeptierend sein muss, sonst wird das Wort nicht akzeptiert.

Folgend ein Beispiel: Betrachte das Wort $w = 010$ , was in dem folgenden Automat eine bestimmte Abfolge von Zuständen einnehmen wird / kann. Es wird hier nicht akzeptiert und ist somit nicht valide, obwohl es “mal in einem akzeptierten Zustand war” Der Automat dazu:
stateDiagram-v2
[*] --> q0
q0 --> q0:0
q0 --> [q1]:1
[q1] --> [q1]:1
[q1] --> q2:0
q2 --> [q1]:0,1

^1720638270109

Zusammenhang von Sprachen und Automaten

Wir sehen hier jetzt schon, dass scheinbar eine gewisse Abhängigkeit zwischen diesen beiden Konstrukten gefunden werden kann.

Wir können sagen, dass ein Automat eine Sprache identifizieren kann, dadurch definiert, welche Worte dieser akzeptieren kann. Also: $L (M) = {w \in Σ^{*} ∣ δ^{*} (w) \in F}$ (Alle Worte, die in der Ausführung mit der Übergangsfunktion einen akzeptierten Zustand haben werden). –> $L (M)$ beschreibt ferner also die Sprache, die der Automat $M$ “sprechen kann”, bzw. die Sprache, bei welcher jedes Wort akzeptiert wird.

[!Question] Gibt es für jede Sprache einen Automaten, der sie spricht/sprechen kann?

Falls nicht, wie sieht die Sprache dann aus?

Grundsätzlich werden wir jede reguläre Sprache erkennen können, also solche, die man mit einem endlichen, deterministischen Automaten bestimmen / definieren kann.

Da diese deterministischen Automaten beispielsweise keinen Speicher haben, werden also Evaluierungen, ob etwa $w^{n} v^{n}$ mit gleichem $n$ existiert nicht ganz möglich sein, weil das der Automat nicht einfach zählen kann! (das wird dann die theo2_TuringMaschineBasics können!)

Da hier die Bindung zu regulären Sprachen sehr hoch ist, wird das der nächste Schwerpunkt sein: 112.03_reguläre_sprachen

Further links:

more advanced automata: 112.04_non_deterministische_automaten

scattered-lenity