Deterministische Endliche Automaten - Versionsgeschichte

Jana am 26. August 2018 um 15:09 Uhr

2018-08-26T15:09:26Z

Jana: Fehlende-Automatenkante-bei Teilbarkeit-durch-3-Fix

2018-08-26T14:57:46Z

Fehlende-Automatenkante-bei Teilbarkeit-durch-3-Fix

Css: /* Formale Definition */

2018-07-29T14:41:45Z

‎Formale Definition

Css am 22. Juli 2018 um 19:37 Uhr

2018-07-22T19:37:22Z

Css: /* Abflusszustand */

2018-07-22T19:34:17Z

‎Abflusszustand

Css: /* = Abflusszustand */

2018-07-22T19:32:29Z

‎= Abflusszustand

Css am 22. Juli 2018 um 19:32 Uhr

2018-07-22T19:32:11Z

Css: /* Formale Definition */

2018-07-22T19:21:34Z

‎Formale Definition

Css: /* Einführung */

2018-07-22T16:45:49Z

‎Einführung

Css am 22. Juli 2018 um 16:34 Uhr

2018-07-22T16:34:11Z

← Nächstältere Version		Version vom 26. August 2018, 15:09 Uhr
Zeile 122:		Zeile 122:
	Wir können einen Automaten jetzt mathematisch exakt definieren: Zunächst haben wir eine Menge $Z$ von Zuständen und eine Teilmenge $E\subseteq Z$ von Endzuständen, und einen Startzustand $s\in Z$. Gegeben ein Alphabet $\cal L$ haben wir eine '''Transitionsfunktion''' $\delta : Z\times{\cal L}\rightarrow Z\cup\{\bot\}$, die jedem Zustand und Zeichen einen neuen Zustand zuordnet, wobei Pfeile die ins Leere zeigen auf $\bot$ abgebildet werden – wir setzen voraus, dass $\bot\not\in Z$. Das Quartupel $(Z, E, s, \delta)$ beschreibt den Automaten damit eindeutig.		Wir können einen Automaten jetzt mathematisch exakt definieren: Zunächst haben wir eine Menge $Z$ von Zuständen und eine Teilmenge $E\subseteq Z$ von Endzuständen, und einen Startzustand $s\in Z$. Gegeben ein Alphabet $\cal L$ haben wir eine '''Transitionsfunktion''' $\delta : Z\times{\cal L}\rightarrow Z\cup\{\bot\}$, die jedem Zustand und Zeichen einen neuen Zustand zuordnet, wobei Pfeile die ins Leere zeigen auf $\bot$ abgebildet werden – wir setzen voraus, dass $\bot\not\in Z$. Das Quartupel $(Z, E, s, \delta)$ beschreibt den Automaten damit eindeutig.

−	Beispielsweise hätten wir für obiges Beispiel, den Automaten der Folgen mit gerade vielen Einsen erkennt, $Z=\{1,2\}$, $E=\{1\}$, $s=1$, $\delta(1,0)=1$, $\delta(1,1)=2$, $\delta(2,0)=0$, $\delta(2,1)=1$.	+	Beispielsweise hätten wir für obiges Beispiel, den Automaten der Folgen mit gerade vielen Einsen erkennt, $Z=\{1,2\}$, $E=\{1\}$, $s=1$, $\delta(1,0)=1$, $\delta(1,1)=2$, $\delta(2,0)=2$, $\delta(2,1)=1$.

@@ Zeile 94: / Zeile 94: @@
            | V           | V             | V
      ---->((1))----1---->(2)------1----->(3)
-             A          | A             |
+          A  A          | A             | |
-             |          | |             |
+          |  |          | |             | |
-             +-----2----+ +------2------+
+          |  +-----2----+ +------2------+ |
 == Alternativen ==

@@ Zeile 117: / Zeile 117: @@
 == Formale Definition ==
-Wir können einen Automaten jetzt mathematisch exakt definieren: Zunächst haben wir eine Menge $Z$ von Zuständen und eine Teilmenge $E\subseteq Z$ von Endzuständen, und einen Startzustand $s\in Z$. Gegeben ein Alphabet $\cal L$ haben wir eine '''Transitionsfunktion''' $\sigma : Z\times{\cal L}\rightarrow Z\cup\{\bot\}$, die jedem Zustand und Zeichen einen neuen Zustand zuordnet, wobei Pfeile die ins Leere zeigen auf $\bot$ abgebildet werden – wir setzen voraus, dass $\bot\not\in Z$. Das Quartupel $(Z, E, s, \sigma)$ beschreibt den Automaten damit eindeutig.
+Wir können einen Automaten jetzt mathematisch exakt definieren: Zunächst haben wir eine Menge $Z$ von Zuständen und eine Teilmenge $E\subseteq Z$ von Endzuständen, und einen Startzustand $s\in Z$. Gegeben ein Alphabet $\cal L$ haben wir eine '''Transitionsfunktion''' $\delta : Z\times{\cal L}\rightarrow Z\cup\{\bot\}$, die jedem Zustand und Zeichen einen neuen Zustand zuordnet, wobei Pfeile die ins Leere zeigen auf $\bot$ abgebildet werden – wir setzen voraus, dass $\bot\not\in Z$. Das Quartupel $(Z, E, s, \delta)$ beschreibt den Automaten damit eindeutig.
-Beispielsweise hätten wir für obiges Beispiel, den Automaten der Folgen mit gerade vielen Einsen erkennt, $Z=\{1,2\}$, $E=\{1\}$, $s=1$, $\sigma(1,0)=1$, $\sigma(1,1)=2$, $\sigma(2,0)=0$, $\sigma(2,1)=1$.
+Beispielsweise hätten wir für obiges Beispiel, den Automaten der Folgen mit gerade vielen Einsen erkennt, $Z=\{1,2\}$, $E=\{1\}$, $s=1$, $\delta(1,0)=1$, $\delta(1,1)=2$, $\delta(2,0)=0$, $\delta(2,1)=1$.

@@ Zeile 113: / Zeile 113: @@
            +----1------+
-Der Automat akzeptiert offensichtlich die gleichen Wörter, und hat keine Pfeile mehr, die ins Leere zeigen.
+Der Automat akzeptiert offensichtlich die gleichen Wörter, und hat keine Pfeile mehr, die ins Leere zeigen. Wir werden, je nach Anwendungsfall, auf diese Form von Automaten zurückgreifen, da sie ja äquivalent ist.
 == Formale Definition ==

@@ Zeile 112: / Zeile 112: @@
            |           |            +-1-+
            +----1------+
 == Formale Definition ==

@@ Zeile 100: / Zeile 100: @@
 == Alternativen ==
-=== Abflusszustand ==
+=== Abflusszustand ===
 Statt Pfeile, die "ins Leere" gehen, wegzulassen, können wir auch festlegen, dass immer alle Pfeile wieder auf einen Zustand zeigen. Um dann Pfeile "ins Leere" zu simulieren, fügen wir einen '''Abflusszustand''' ($\bot$) hinzu. Auf ($\bot$) sollen alle Pfeile die sonst ins Leere gehen würden zeigen, außerdem führen alle Pfeile von ($\bot$) weg wieder zurück zu ($\bot$), und ($\bot$) ist kein Endzustand. Aus obigem Beispiel würde dann

@@ Zeile 2: / Zeile 2: @@
 Wir wollen uns nun ein einfaches Maschinenmodell ansehen, mit dem man bestimmte Wörter erkennen kann. Das Ganze ist zwar inspiriert von echten Schaltkreisen, und man kann anhand dessen auch theoretisch Maschinen bauen, ist aber ein rein formales Konstrukt.
-Zunächst überlegen wir uns, dass eine Maschine ein Wort am Sinnvollsten Zeichen für Zeichen einliest und verarbeitet. Wenn ein Zeichen eingelesen ist, muss sich irgendetwas in der Maschine verändern, das heißt, eine Maschine hat irgendeinen '''Zustand'''. Das heißt, das Einlesen eines Zeichens führt eine Maschine von einem Zustand in einen anderen Zustand über.
+Zunächst überlegen wir uns, dass eine Maschine ein Wort am sinnvollsten Zeichen für Zeichen einliest und verarbeitet. Wenn ein Zeichen eingelesen ist, muss sich irgendetwas in der Maschine verändern, das heißt, eine Maschine hat irgendeinen '''Zustand'''. Das heißt, das Einlesen eines Zeichens führt eine Maschine von einem Zustand in einen anderen Zustand über.
 Gehen wir der Einfachheit halber davon aus, dass eine bestimmte Maschine nur endlich viele Zustände hat, und benennen wir diese Zustände mit Zahlen $1,\ldots,n$. Das Einfachste, was so eine Maschine beim Einlesen eines Zeichens tun kann ist, entscheiden, zu welchem Zustand sie Springen soll. Man kann sich einen so einfachen Zustand also so vorstellen:

← Nächstältere Version		Version vom 22. Juli 2018, 16:34 Uhr
Zeile 102:		Zeile 102:
	Wir können einen Automaten jetzt mathematisch exakt definieren: Zunächst haben wir eine Menge $Z$ von Zuständen und eine Teilmenge $E\subseteq Z$ von Endzuständen. Gegeben ein Alphabet $\cal L$ haben wir eine '''Transitionsfunktion''' $\sigma : Z\times{\cal L}\rightarrow Z\cup\{\bot\}$, die jedem Zustand und Zeichen einen neuen Zustand zuordnet, wobei Pfeile die ins Leere zeigen auf $\bot$ abgebildet werden – wir setzen voraus, dass $\bot\not\in Z$. Das Tripel $(Z, E, \sigma)$ beschreibt den Automaten damit eindeutig.		Wir können einen Automaten jetzt mathematisch exakt definieren: Zunächst haben wir eine Menge $Z$ von Zuständen und eine Teilmenge $E\subseteq Z$ von Endzuständen. Gegeben ein Alphabet $\cal L$ haben wir eine '''Transitionsfunktion''' $\sigma : Z\times{\cal L}\rightarrow Z\cup\{\bot\}$, die jedem Zustand und Zeichen einen neuen Zustand zuordnet, wobei Pfeile die ins Leere zeigen auf $\bot$ abgebildet werden – wir setzen voraus, dass $\bot\not\in Z$. Das Tripel $(Z, E, \sigma)$ beschreibt den Automaten damit eindeutig.

−	Beispielsweise hätten wir für obiges Beispiel, den Automaten der Folgen mit gerade vielen Einsen erkennt, $Z=\{1,2\}$, $E=\{1\}$, $\sigma(1,0)=1$, $\sigma(1,1)=2$, $\sigma(2,0)=~~\bot~~$, $\sigma(2,1)=1$.	+	Beispielsweise hätten wir für obiges Beispiel, den Automaten der Folgen mit gerade vielen Einsen erkennt, $Z=\{1,2\}$, $E=\{1\}$, $\sigma(1,0)=1$, $\sigma(1,1)=2$, $\sigma(2,0)=0$, $\sigma(2,1)=1$.