Deterministische Endliche Automaten
Inhaltsverzeichnis
Einführung
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.
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:
+------a1-------->
|
(n)-----a2-------->
| ...
|
+------an-------->
wobei $n$ die Nummer des Zustandes ist, und die $a_i$ die Zeichen des endlichen Alphabets sind. Die Pfeile zeigen dabei jeweils entweder wieder auf Zustände, oder "ins Leere". Eine Maschine, die sich aus mehreren solchen einfachen Zuständen zusammensetzt, nennt man einen (deterministischen endlichen) Automaten.
Ein sehr einfacher endlicher Automat ist zum Beispiel gegeben durch
A
|
1
|
(1)---0--->(2)---0--->
A |
| |
+----1-----+
Der Einfachheit halber lässt man die Pfeile, die "ins Leere" zeigen, weg:
(1)---0--->(2)
A |
| |
+----1-----+
Einer der Zustände muss derjenige sein, in dem der Automat am Anfang, wenn noch garnichts eingelesen wurde, ist. Es hat sich eingebürgert, einen Pfeil der "aus dem Leeren" kommt, dafür zu benutzen:
---->(1)---0--->(2)
A |
| |
+----1-----+
Nehmen wir nun an, dieser Automat lese das Wort $0101$ ein. Das erste Zeichen ist $0$, und wir sind im Zustand (1). Der Zustand (1) hat einen Pfeil mit der Beschriftung $0$ zu Zustand (2). Das heißt, danach sind wir in Zustand (2).
Das nächste Zeichen ist $1$. Von (2) geht ein Pfeil mit der Beschriftung $1$ zum Zustand (1), das heißt, danach sind wir wieder im Zustand (1).
Das dritte Zeichen ist $0$. Analog zu vorhin gehen wir zu Zustand (2). Das vierte Zeichen ist wieder $1$, und wir gehen wieder zum Zustand (1). Das Wort ist vollständig eingelesen.
Natürlich bringt es uns nicht viel, Wörter nur einlesen zu können. Was wir wollen, ist, dass der Automat eine Entscheidung trifft: Er kann ein Wort akzeptieren oder ablehnen. Fürs Akzeptieren definieren wir Endzustände, und sagen, wenn der Automat nach dem Einlesen des Wortes in einem Endzustand ist, dann gilt das Wort als akzeptiert. Endzustände stellen wir dar mit zwei Kreisen statt einem.
---->(1)---0--->((2))
A |
| |
+----1------+
Das Wort $010$ wird zum Beispiel akzeptiert: Nach dem vollständigen Einlesen sind wir bei Zustand (2), welches ein Endzustand ist.
Wann immer ein Wort nicht akzeptiert wird, gilt es als abgelehnt. Das Wort $0101$ wird zum Beispiel abgelehnt: Am Ende ist man in Zustand (1), welcher kein Endzustand ist. Das Wort $011$ wird ebenfalls abgelehnt: nachdem wir $01$ eingelesen haben, sind wir in Zustand (1), aber der $1$-Pfeil von (1) zeigt ins Leere.
Beispiele
- Der folgende Automat erkennt genau $\varepsilon$:
---->((1))
- Der folgende Automat erkennt beliebig viele Wiederholungen von "abc":
---->((1))---a--->(2)---b--->(3)
A |
| |
+----------c-----------+
- Der folgende Automat erkennt beliebige Folgen von $0$ und $1$ mit gerade vielen $1$-en:
+------------+
| +--------+ |
| | | |
V V | |
---->((1))---0---+ |
| |
1 |
| |
V |
+-(2)----1-----+
| A
0 |
| |
+--+
- Der folgende Automat erkennt, ob die Summe der Zahlen einer Folge von Nullen, Einsen und Zweien durch drei Teilbar ist:
+-+ +-+ +-+
| | | | | |
0 | 0 | 0 |
| V | V | V
---->((1))----1---->(2)------1----->(3)
A A | A | |
| | | | | |
| +-----2----+ +------2------+ |
+--------------1----------------+
Alternativen
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
+------------------------+
| | +--0--+
1 V | |
| +-->(_|_)<---+
---->(1)---0--->((2))--0---+ | A
A | | |
| | +-1-+
+----1------+
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
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)=2$, $\delta(2,1)=1$.
