Deterministischer Endlicher Automat: Unterschied zwischen den Versionen
Zur Navigation springen
Zur Suche springen
(Die Seite wurde neu angelegt: „Ein deterministischer endlicher Automat erhält ein Wort als Eingabe und akzeptiert dieses Wort oder nicht. Die Menge der akzeptierten Wörter bildet die durc…“) |
|||
| Zeile 1: | Zeile 1: | ||
Ein deterministischer endlicher Automat erhält ein Wort als Eingabe und akzeptiert dieses Wort oder nicht. | 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'''. | Die Menge der akzeptierten Wörter bildet die durch den deterministischen endlichen Automaten dargestellte '''Sprache'''. | ||
| Zeile 10: | Zeile 10: | ||
* Z ist eine endliche, nicht leere Menge von '''Zuständen''' Z | * Z ist eine endliche, nicht leere Menge von '''Zuständen''' Z | ||
* d: Z x A → Z ist die '''Zustandsübergangsfunktion''' | * d: Z x A → Z ist die '''Zustandsübergangsfunktion''' | ||
* q<sub>0</sub> & | * q<sub>0</sub> ∈ Z ist der '''Anfangszustand''' | ||
* E ⊆ Z ist die Menge der '''Endzustände''' | * E ⊆ Z ist die Menge der '''Endzustände''' | ||
Die Zustandsübergangsfunktion kann durch einen '''Übergangsgraphen''' oder durch eine Tabelle dargestellt werden. | |||
=Beispiel= | |||
Der '''007-Automat''': | |||
Zur Sprache gehören all diejenigen Ziffernfolgen, die an beliebiger Stelle die Ziffernfolge "007" enthalten. | |||
* '''Eingabealphabet''': A = {0, 1, ..., 9} | |||
* '''Zustände''': Z = {q<sub>0</sub>, q<sub>1</sub>, q<sub>2</sub>, q<sub>3</sub>, q<sub>4</sub>} | |||
* '''Zustandsübergangsfunktion''' wird durch den Übergangsgraph unten dargestellt. | |||
* '''Anfangszustand''': q<sub>0</sub> | |||
* '''Endzustände''': {q<sub>0</sub>} | |||
Version vom 22. Februar 2015, 21:44 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.
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.
Beispiel
Der 007-Automat:
Zur Sprache gehören all diejenigen Ziffernfolgen, die an beliebiger Stelle die Ziffernfolge "007" enthalten.
- Eingabealphabet: A = {0, 1, ..., 9}
- Zustände: Z = {q0, q1, q2, q3, q4}
- Zustandsübergangsfunktion wird durch den Übergangsgraph unten dargestellt.
- Anfangszustand: q0
- Endzustände: {q0}