cards-deck: date-created: 2024-02-21 12:07:36 date-modified: 2024-07-10 09:34:20

Nicht-deterministische Automaten | NDA

part of [[112.00_anchor_overview]] requires 112.02_deterministische_automaten also linked to theo2_SprachenNichtRekursiv

Motivation

Bis dato haben wir deterministische Automaten betrachtet, welche in ihrer Übergangsfunktion $\delta$ genau eindeutig eine Eingabe + Zustand zu einem neuen Zustand gebracht hat. Betrachten wir jetzt einen nicht-deterministischen Automaten, dann erlauben wir hier, dass die Übergangsfunktion $\delta$ mehrere Berechnungspfade haben kann, und diese parallel erkunden/berechnen kann.

Das heißt ferner, dass wir etwa bei einem Zustand zwei Wege haben können, von denen eine Eingabe in verschiedene “Richtungen” übergehen bzw. verweilen wird. Diese Pfade werden dann beide parallel bearbeitet bzw betrachtet und verarbeitet. Dabei ist am Ende aber wichtig, dass mindestens einer der gegangenen Pfade akzeptierend ist, damit die ganze Eingabe als akzeptierend gesetzt wird/werden kann.

Motivation von Nicht-Deterministischen Konzepten

Nicht-Determinismus ist ein theoretisches Konzept, das praktisch nicht realisierbar ist/scheint. Dennoch betrachten wir es als Konzept, auch wenn wir es nicht umsetzen können.

[!Tip] Gründe für nicht-determinismus

Nicht-Determinismus liefer uns eine gewisse Obermenge aller möglichen Berechnungen die ein Automat durchführen könnte.

Warum ist das Konzept von Nicht-Determinismus relevant/wichtig? Was wäre ein Vorteil gegenuber determ. Systeme? #card

Es ist insofern interessant bzw wichtig, da man hier sehen kann, dass in bestimmten Typen von Automaten - also theo2_TuringMaschineBasics etwa - der Nicht-Determinismus keine erhöhte / verbesserte Berechnungskraft liefern kann.

Weiterhin ist ein Vorteil von nicht-deterministischen Systemen, dass ihre Versionen meist deutlich ( eher exponentiell) weniger Zustände haben, als die deterministischen Varianten –> Das liegt daran, dass man hier nicht jede Kombination abdecken muss, sondern bei nicht-det Automaten die “Ausführung” dazu führt, dass manche Zustände - die deterministisch auftreten müssen - nicht passieren.

[!Tip] Streben nach Simulation von nicht-det-Automaten

Daher liegt es nahe, dass dann die Idee / Funktionalität eines nicht-deterministischen Automaten angestrebt wird, und so von Maschinen - die det sind - simuliert werden möchte.

Aus dieser Betrachtung wird es jetzt auch wichtig, dass betrachten kann oder möchte, ob ein NFA mehr berechnen / abdecken kann, als es ein DFA kann / wird.

Warum brauchen wir Nicht-Determinismus ?

In vielen Bereichen der Informatik kann der Zufall ein sehr mächtiges Werkzeug sein und bestimmte Prozesse beschleunigen und verbessern. Als Beispiel können Randominiserte Algorithmen dienen [[111.99_algo_randomized_algorithms]]

Quicksort basiert beispielsweise auf dem Prinzip der randomisierten Wahl von Pivot-Elementen.

Idee nicht deterministischer Automaten :

Bis dato war die Übergangsfunktion deterministisch geprägt: Wir wissen genau, welche Zustände aus einem gegebenen Zustand folgen können, und welche Eingaben dafür notwendig sind. weswegen wollen wir jetzt nichtdeterministische Automaten konstruieren? Was könnte ihr Vorteil sein, wie funktionieren sie ? #card

Wenn wir jetzt für einen Zustand also einfach mehrere Pfade angeben, die bei einer Eingabe, dann alle gegangen werden sollten, haben wir keinen genauen Weg, der garantiert abgelaufen wird, da beispielsweise 2 Pfade bei der Eingabe einer 1 genommen werden können.

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

In diesem Beispiel kann der Automat bei einer Eingabe 0 vom Initialstart $q_1$ zwei Wege einschlagen: $q_2\vee q_3$ welchen dieser Wege wir genau gehen, wird sich noch ergeben, denn: Der Automat muss sich nicht für einen Weg entscheiden. Er führt einfach alle möglichen Berechnungen parallel aus. -> Aus Betrachtung von Software können wir uns das als parallele Ausführung des Automaten vorstellen, immer dann wenn eine Eingabe ( etwa 0) zu zwei verschiedenen Wegen, von einem Zustand aus, führen kann.

Definition | nicht deterministischer endlicher Automat

Wir wollen ferner den neuen Automaten definieren, dabei ist die Konstruktion relativ ähnlich zu unseren 112.02_deterministische_automaten, hat aber eine neue / andere Übergangsfunktion

[!Definition] Definition | Wir nennen einen nicht-deterministischen endlichen Automaten ein 5-Tupel $N=\ast Q,\Sigma ,\delta ,q_0,F$ wobei ferner:

Was beschreiben die einzelnen Elemente des Tupels? #card

• $Q$ eine endliche Menge, der Zustände ist
• $\Sigma$ die Menge der Symbole bzw. einfach die Sprache ist
• $\delta :Q\times (\Sigma \cup \{\epsilon \})\to \mathcal{P}(Q)$ die neue Übergangsfunktion

Berechnen |

Wir erlauben hier immer, dass nicht deterministische Automaten / Strukturen, das leere Wort $\{\epsilon \}$ erlauben.

[!Req]

Intuitive Idee, was man mit den Automaten machen könnte.

Betrachten wir zwei Sprachen:

$A:=\{x\in \{0,1\}\mid \text{ Anzahl 0 gerade}\}$ $B:=\{x\in \{0,1\}\mid \text{ Anzahl 1 ungerade}\}$

–> sie sind $\in REG$ weil wir sie entsprechend mit einem DEA erzeugen bzw erkennen / akzeptieren könn(t)en.

Wir “fragen” jetzt, ob die Konkatenation der beiden Sprachen $AB=\{ab\mid a\in A,b\in B\}$ mit einem Automaten dargestellt werden kann. -> Ja ist möglich, per Definition.

Aber wie könnte besagter Automat aussehen, der das realisiert? #card

Es müsste eine Zerlegung des Strings passieren, da er bei der “Verarbeitung” teilweise akzeptiert / nicht akzeptiert werden könnte.

(Möglichkeit ohne nicht-Determinismus): (gemäß Sipser):

Sei $\mid w\mid =n$ Der Automat muss zunächst einen ersten Teil $a$ des Wortes von Länge $m$ betrachten und dann testen wir ob $a\in A$ - also mit dem ersten Automat $M_A$ Dann muss er testen, ob $be\in w=ab$ in $\in B$ liegt - also ob wir jetzt auf $M_B$ umschalten dürfen. ( Das heißt, wie haben $a$ bereits abgeschlossen).

Dieser Prozess muss dann $\forall 0\le m\le n$ wiederholt werden!.

-> Das heißt alle möglichen Werte des “Umschaltpunktes” $m$ gleichzeitig ausprobieren.

Alternative Wortwahl: Er muss “irgendwann an einer beliebigen Stelle $m$ umschalten” –> das klingt vielleicht nicht-deterministisch, ist es aber nicht.

Betrachten wir diesen Automaten, dann betrachtet er also genau $ab$ und somit versteht er zuerst $a$ und kann danach $b$ noch verstehen. –> Dabei gilt hier also nur, dass wir das Wort so aufteilen können, dann diese Eigenschaften für $A$ und $B$ erfüllt werden ( auch wenn im gesamte Wort selbst die beiden Eigenschaften nicht erfüllt werden).

Aus diesem Automaten stellt sich die Frage, wann denn von dem einen Automat zum anderen gesprungen werden sollte –> also wann $\epsilon$ ausgelöst und wir somit springen werden / können.

Das ist insofern relevant, weil wir hier sehen, dass es sehr viele Möglichkeiten geben kann, bei denen dieser Verlauf stattfindet. Wir müssten theoretisch alle davon abdecken.

Wir sehen hierbei, dass bei der Berechnung eines NDAs immer ein Baum aufgespannt wird, der sich je stetig pro Zustand weiter aufteilen/fächern kann.

Tiefe / Größe von Berechnungsbäumen:

Die Tiefe des Baumes ist abhängig vom Alphabet und der Menge von Eintragen:

[!Tip] Größe des Entscheidungs bzw. Berechnungsbaumes

Wie groß ist ein Entscheidungsbaum für einen NDFA, bzw. wovon hängt es ab? #card

Der Berechnungsbaum wäçhst in seiner Größe (also der Menge von Zuständen, die nicht deterministisch passieren können) in einer Größe von $$\mid \Sigma {\mid }^n$$ wobei $n$ die Menge von Zuständen beschreibt.

Beispiel

Ein weiteres Beispiel aus dem Buch Sipser:

stateDiagram-v2
classDef accepted fill:#fff,color:#000

[*]-->q1
q1-->q1:0,1
q1-->q2:1
q2-->q3:0,$\epsilon$
q3-->q4:1
q4-->q4:0,1

q4:::accepted

Bei diesem Beispiel ist der Übergang von $q_1$ bei einer Eingabe von 1 nicht deterministisch, weiterhin auch nicht der Übergang von $q_2$, da wir $ϵ$ also ein leeres Wort antreffen. Der Berechnungsbaum - parallel verlaufend! - ist für dieses Beispiel sehr ausführlich: ![[Pasted image 20230427002006.png]]

Kann ein NFA mehr als ein DFA?

(eigentlich nicht).

[!Definition] Äquivalenz von zwei Automaten $M_1,M_2$ (nicht oder det)

Betrachten wir zwei Automaten, wann nennen wir sie Äquivalent? Was hilft das zur Aussage der Äquialenz von DFA / NFA #card

Wir nennen zwei Automaten $M_1,M_2$ ( ob sie jetzt deterministisch oder nicht-deterministisch sind) heißen äquivalent, wenn sie die gleiche Sprache erkennen. Ferner also auch die gleiche Sprache erkennen kann. $$L(M_1)=L(M_2)$$

Ferner folgt daraus jetzt auch, dass wir dann eine Äquivalenz zwischen einem NFA und DFA schaffen könnten.

Satz | Jeder NFA hat auch einen DFA

[!Proposition]

Zu jedem NFA $N$ gibt es einen äquivalenten DFA $M$

Wie könnte man das beweisen? Was wäre ein Ansatz dafür? #card

Der Beweis zu diesem Theorem ist schwierig zu konstruieren, aber man kann in der Betrachtung darüber nachdenken, dass man für den nicht-deterministischen Automaten einfach nur alle Zustände, die eintreten könnten, erhalten. Wir müssen also von nicht-det zu det Automaten die Übergangsfunktionen, und auch die Zustände adaptieren bzw. überarbeiten.

Beweis der Aussage:

Seit entsprechend $N=(Q,\Sigma ,\delta ,q_0,F)$ ein NFA, der eine Sprache $L$ akzeptiert. Wir konstruieren jetzt den DFA $M=(Q^{\prime }.\Sigma ,{\delta }^{\prime },q_0^{\prime },F^{\prime })$ - das Alphabet bleibt gleich, kann man also so lassen.

wir wollen Epsilon-Übergänge - die es im DFA nicht gibt - mit einer neuen Übersetzung / Notation umwandeln:

Übersetzung von NFA zu DFA

Wie sind die Abläufe, um einen NFA in einen DFA zu übersetzen? #card

1. Potenzmenge des DFA machen –> also $2^{\mid Q\mid }$
2. Startzustand definieren –> was kann beim Startzustand erreicht werden - etwa durch $\epsilon$ als Eingabe vom Startzustand?
3. Alle Teilmengen die einen akzeptierenden Zustand aufweisen, werden auch wieder akzeptierend sein
4. Die Übergänge werden jetzt nach und nach konstruiert
   1. Wichtig bei $\epsilon$ ist, dass wir schauen müssen, was dann mit validen Einträgn in diesem Bereich passiert. Im folgenden Beispiel wird etwa das $\epsilon$ damit übersetzt, dass man einen $\varnothing$ Zustand einführt.

Man kann hierbei nicht erreichbare Zustände entfernen, da sie keinen Mehrwert bieten bzw. keinen Inhalt haben.

[!Important] Da DFA = NFA ==> Beweise einfacher Da wir jetzt gezeigt haben, dass für jeden NFA auch ein DFA existiert ( und vice-versa) können wir dann in Beweisen und Betrachtungen immer auch mit einem NFA argumentieren, da wir wissen, dass sie auch ein DFA sein kann.

Wir können durch NFa Beweise stark vereinfachen, weil es hier etwa möglich wird, eine Vereinigung relativ einfach darzustellen, indem man einfach einen Startzustand setzt, von welchem dann mit $\epsilon$ in beide Unterautomaten - also von jeder Sprache - gesprungen wird. Da es NFA ist, werden wahrscheinlich beide Automaten erreicht und durchlaufen.

Beweis | Abgeschlossenheit der Verkettung

Wir haben zuvor betrachtet, dass die Klasse der $REG$ abgeschlossen ist unter der Verkettung, also: $$L_1,L_2\in REG⟹L_1{L}_2\in REG$$ das kann man jetzt durch eine Skizze beweisen, aber auch formal:

Skizze:

formaler Beweis: WIr wollen jetzt einen neuen Automaten bilden, der beide vermischt. Wir haben bereits zwei Automaten: $$\begin{array}{r}{M}_1=(Q_1,\Sigma ,{\delta }_1,q_1,F_1)\\ M_2=(Q_2,\Sigma ,{\delta }_2,q_2,F_2)\end{array}$$

Wir können dann jetzt den neuen Automaten folgend bilden:

• $Q=Q_1\cup Q_2$ -> wobei es eine direkte Vereinigung ist, da bei Überlappung die Zustände neu benannt werden -> wir dürfen sie nicht verlieren
• $q=q_1$ -> also der Anfang von Automat $M_1$, da dieser in der Verkettung als erstes kommt.
• $F=F_2$ -> Wir akzeptieren ja nur Worte, die $L_1{L}_2$ sind, und das heißt, wir enden mit einem Wort $L_2$ $⟹$ das Wort ist also im Bereich von $F_2,M_2$
• DIe Übergangsfunktion ist jetzt schwierig zu konstruieren.

Die Kleen’sche Hülle $\in REG$ #card

Auch das könen wir beweisen, indem wir darauf achten, dass wir einen DFA bilden können, der das löst.