Deterministischer Endlicher Automat: Unterschied zwischen den Versionen
| Zeile 14: | Zeile 14: | ||
Deterministische endliche Automaten können als Java-Programm realisiert werden. Ein solches Programm nennt man '''[[Parser]]'''. | Deterministische endliche Automaten können als Java-Programm realisiert werden. Ein solches Programm nennt man '''[[Parser]]'''. | ||
=Beispiel= | =Beispiel= | ||
| Zeile 53: | Zeile 42: | ||
||<b>q<sub>3</sub></b> || || || || 0..9 | ||<b>q<sub>3</sub></b> || || || || 0..9 | ||
|} | |} | ||
=Definition= | |||
Ein deterministischer, endlicher Automat wird durch ein 5-Tupel (A, Z, d, q<sub>0</sub>, E) spezifiziert: | |||
* Das '''Eingabealphabet''' A ist eine endliche, nicht leere Menge von Symbolen. Buchstaben des Eingabealphabetes werden in der Regel ''klein'' geschrieben. | |||
* Z ist eine endliche, nicht leere Menge von '''Zuständen''' Z | |||
* d: Z x A → Z ist die '''Zustandsübergangsfunktion''' | |||
* q<sub>0</sub> ∈ Z ist der '''Anfangszustand''' | |||
* E ⊆ Z ist die Menge der '''Endzustände''' | |||
Die Zustandsübergangsfunktion kann durch einen '''Übergangsgraphen''' oder durch eine Tabelle dargestellt werden. | |||
=Beziehung zu regulären Sprachen und regulären Grammatiken= | =Beziehung zu regulären Sprachen und regulären Grammatiken= | ||
| Zeile 58: | Zeile 57: | ||
* '''Zu jedem deterministischen endlichen Automaten gibt es eine [[reguläre Grammatik]].''' <br>''Diese lässt sich leicht aus dem Übergangsgraphen konstruieren.'' | * '''Zu jedem deterministischen endlichen Automaten gibt es eine [[reguläre Grammatik]].''' <br>''Diese lässt sich leicht aus dem Übergangsgraphen konstruieren.'' | ||
* '''Zu jeder [[reguläre Grammatik|regulären Grammatik]] gibt es einen deterministischen endlichen Automaten.'''<br> ''Dazu erstellt man aus der regulären Grammatik erst einen [[Nicht-deterministischer endlicher Automaten|Nicht-deterministischen endlichen Automaten]] und aus diesem einen deterministischen endlichen Automaten (mühsam, aber es ist bewiesen, dass das immer geht!) | * '''Zu jeder [[reguläre Grammatik|regulären Grammatik]] gibt es einen deterministischen endlichen Automaten.'''<br> ''Dazu erstellt man aus der regulären Grammatik erst einen [[Nicht-deterministischer endlicher Automaten|Nicht-deterministischen endlichen Automaten]] und aus diesem einen deterministischen endlichen Automaten (mühsam, aber es ist bewiesen, dass das immer geht!) | ||
=Grenzen= | |||
Nicht jede Sprache kann durch einen deterministischen endlichen Automaten erkannt werden. | |||
Die wesentliche Grenze ist hierbei, dass der Automat '''endlich''' sein muss. | |||
==Beispiel== | |||
Gegeben ist eine Sprache, die aus dem Alphabet A = {a, b} besteht. | |||
Zur Sprache sollen die Wörter der Form <code>a<sup>n</sup>b<sup>n</sup></code> gehören, d.h. alle Wörter für die gilt: | |||
* erst beliebig viele a | |||
* dann <u>genauso viele</u> b. | |||
'''Für diese Sprache gibt es keinen deterministischen endlichen Automaten!''' | |||
'''Begründung:''' Der Automat muss sich "merken" können, wie viele a vorgekommen sind. Dafür bräuchte er eine unbegrenzte Menge von Zuständen, denn es ist nicht festgelegt, wie viele Buchstaben "a" kommen, bevor man zu "b" übergeht. | |||
==Weitere Beispiele== | |||
* Die <u>spiegelsymmetrische</u> Sprache: Jedes Wort soll in der Mitte eine Spiegelachse haben, d.h. die erste Worthälfte soll spiegelsymmetrisch zur zweiten Worthälfte sein. | |||
* Die Sprache der <u>Doppelwörter</u>: Zu dieser Sprache gehören genau die Wörter, die aus zwei gleichen Wörtern bestehen. | |||
Version vom 23. Februar 2015, 07:56 Uhr
Ein deterministischer endlicher Automat erhält ein Wort als Eingabe und akzeptiert dieses Wort oder nicht.
Die Menge der akzeptierten Wörter bildet die durch den deterministischen endlichen Automaten dargestellte Sprache.
Sprachen, die von deterministischen endlichen Automaten akzeptiert werden, heißen reguläre Sprache.
Zu unterscheiden ist der deterministische endliche Automat vom Nicht-deterministischen endlichen Automaten.
Deterministische endliche Automaten können als Java-Programm realisiert werden. Ein solches Programm nennt man Parser.
Beispiel
Der KGB-Automat:
Der KGB-Automat erkennt Wörter, die nur aus den Ziffern 0,...,9 bestehen und die irgendwo die Zahlenkette "007" enhalten.
- Eingabealphabet: A = {0, 1, ..., 9}
- Zustände: Z = {q0, q1, q2, q3}
- Die Zustandsübergangsfunktion wird durch den Übergangsgraph (rechts) oder die Übergangstabelle (unten) dargestellt.
- Anfangszustand: q0 (im Graph: ein Dreieck)
- Endzustände: {q3} (im Graph: ein Doppelkreis)
Die Zustandsübergangsfunktion als Tabelle dargestellt:
| q0 | q1 | q2 | q3 | |
|---|---|---|---|---|
| q0 | 1..9 | 0 | ||
| q1 | 1..9 | 0 | ||
| q2 | 1..6,8,9 | 0 | 7 | |
| q3 | 0..9 |
Definition
Ein deterministischer, endlicher Automat wird durch ein 5-Tupel (A, Z, d, q0, E) spezifiziert:
- Das Eingabealphabet A ist eine endliche, nicht leere Menge von Symbolen. Buchstaben des Eingabealphabetes werden in der Regel klein geschrieben.
- Z ist eine endliche, nicht leere Menge von Zuständen Z
- d: Z x A → Z ist die Zustandsübergangsfunktion
- q0 ∈ Z ist der Anfangszustand
- E ⊆ Z ist die Menge der Endzustände
Die Zustandsübergangsfunktion kann durch einen Übergangsgraphen oder durch eine Tabelle dargestellt werden.
Beziehung zu regulären Sprachen und regulären Grammatiken
- Sprachen, die von deterministischen endlichen Automaten akzeptiert werden, heißen reguläre Sprache.
- Zu jedem deterministischen endlichen Automaten gibt es eine reguläre Grammatik.
Diese lässt sich leicht aus dem Übergangsgraphen konstruieren. - Zu jeder regulären Grammatik gibt es einen deterministischen endlichen Automaten.
Dazu erstellt man aus der regulären Grammatik erst einen Nicht-deterministischen endlichen Automaten und aus diesem einen deterministischen endlichen Automaten (mühsam, aber es ist bewiesen, dass das immer geht!)
Grenzen
Nicht jede Sprache kann durch einen deterministischen endlichen Automaten erkannt werden.
Die wesentliche Grenze ist hierbei, dass der Automat endlich sein muss.
Beispiel
Gegeben ist eine Sprache, die aus dem Alphabet A = {a, b} besteht.
Zur Sprache sollen die Wörter der Form anbn gehören, d.h. alle Wörter für die gilt:
- erst beliebig viele a
- dann genauso viele b.
Für diese Sprache gibt es keinen deterministischen endlichen Automaten!
Begründung: Der Automat muss sich "merken" können, wie viele a vorgekommen sind. Dafür bräuchte er eine unbegrenzte Menge von Zuständen, denn es ist nicht festgelegt, wie viele Buchstaben "a" kommen, bevor man zu "b" übergeht.
Weitere Beispiele
- Die spiegelsymmetrische Sprache: Jedes Wort soll in der Mitte eine Spiegelachse haben, d.h. die erste Worthälfte soll spiegelsymmetrisch zur zweiten Worthälfte sein.
- Die Sprache der Doppelwörter: Zu dieser Sprache gehören genau die Wörter, die aus zwei gleichen Wörtern bestehen.