Inhaltsverzeichnis
Einstieg Automatentheorie
In den Abiturvorgaben gehören endliche Automaten und formale Sprachen zum Bereich III.
- Modellieren kontextbezogener Problemstellungen als deterministische endliche Automaten
- Darstellung von deterministischen endlichen Automaten als Graph und als Tabelle
- Formale Sprachen: Reguläre Sprachen und ihre Grammatiken
Dabei bedeutet deterministisch, das die Ausgabe des Automaten in Abhängigkeit von Eingabe und Zustand eindeutig ist, und endlich, dass die Menge der Eingaben und Ausgaben begrenzt ist.
Was haben ein Colaautomat und eine Fahrradklingel gemeinsam?
s. auch Bernard Schriek, Informatik mit Java, Band III, S. 110
- beide werden bedient
- „ich muss etwas geben um etwas zu bekommen“ - Eingabe und Ausgabe
- beide haben einen Mechanismus
- beide sind störanfällig
Beim Colaautomaten hängt die Ausgabe vom Zustand des Automaten bei der Eingabe ab.
Das Verhalten eines Automaten lässt sich in einer Zustandstabelle erfassen und durch ein Zustandsdiagramm veranschaulichen.
Zustandstabelle des Colaautomaten
Annahme: Der Automat nimmt nur 1€-Münzen an, eine Cola kostet genau 1€. Der Zustand „geladen“ entspricht dabei einem Automaten, in den schon 1€ eingeworfen wurde, ein ungeladener Automat erwartet einen Geldeinwurf.
Zustand | Eingabe | Folgezustand | Ausgabe |
---|---|---|---|
ungeladen | 1€ | geladen | nichts |
ungeladen | Geld zurück | ungeladen | nichts |
ungeladen | Cola ausgeben | ungeladen | nichts |
geladen | 1€ | geladen | 1€ |
geladen | Geld zurück | ungeladen | 1€ |
geladen | Cola ausgeben | ungeladen | Cola |
Zustandsdiagramm des Colaautomaten
Die Übergänge werden hier (JFLAP) in der Form Eingabe ; Ausgabe beschriftet (eine andere Notation wäre Eingabe / Ausgabe). Wird nichts ausgegeben, kann das Ausgabefeld auch leer gelassen werden, dann würde anstat - ein für die nicht definierte Ausgabefunktion erscheinen.
Formale Beschreibung
Ein endlicher Automat A lässt sich als Sechstupel beschreiben: 1)
Die Symbole stehen dabei im Einzelne für die folgenden Eigenschaften des Automaten:
: endliche Menge der Zustände, im Beispiel Colaautomat
= {ungeladen, geladen}
: endliche Menge der Eingaben, im Beispiel
= {1€, Cola ausgeben, Geld zurück}
: endliche Menge der Ausgaben, im Beispiel
= {1€, Cola}
x
: Übergangsfunktion, die aus einer Zustands-Eingabekombination den Folgezustand ermittelt, z.B.
(ungeladen, 1€) = geladen oder
(geladen, Cola ausgeben) = ungeladen
x
: Ausgabefunktion, die aus einer Zustands-Eingabekombination die eindeutige Ausgabe ermittelt, z.B.
(geladen, Cola ausgeben) = Cola
: Anfangszustand, wird im Beispiel festgelegt auf
= ungeladen
Weitere Beispiele für deterministische endliche Automaten
Transduktoren (Mealy-Automaten)
Transduktoren liefern Ausgabe. Beim Mealy-Automaten hängt die Ausgabe vom durchlaufenen Zustandswechsel ab.2)
Negierungsautomat mit zwei Zuständen, der 0 in 1 und 1 in 0 umwandelt
Q = {q0, q1},
= {0, 1},
= {0,1}
(hier steht | für 'oder')
Zustand | Eingabe | Folgezustand | Ausgabe |
---|---|---|---|
q0 | 0 | q1 | 1 |
q0 | 1 | q0 | 0 |
q1 | 0 | q1 | 1 |
q1 | 1 | q0 | 0 |
Negierungsautomat mit einem Zustand
Zeichenersetzungsautomat
Q = {q0, q1},
= {0, 1},
= {f,w}, Umwandlungsregeln: 0 → f 1 → w
Zustand | Eingabe | Folgezustand | Ausgabe |
---|---|---|---|
q0 | 0 | q0 | f |
q0 | 1 | q1 | w |
q1 | 0 | q0 | f |
q1 | 1 | q1 | w |
Zyklische Zeichenvertauschung
Q = {q0, q1, q2, q3}, = {a, b, c, d},
= {a, b, c, d}, Umwandlungsregeln: a → b, b → c, c → d, d → a
Zustand | Eingabe | Folgezustand | Ausgabe |
---|---|---|---|
q0 | a | q | b |
q0 | b | q | c |
q0 | c | q | d |
q0 | d | q | a |
q1 | a | q | b |
q1 | b | q | c |
q1 | c | q | d |
q1 | d | q | a |
q2 | a | q | b |
q2 | b | q | c |
q2 | c | q | d |
q2 | d | q | a |
q3 | a | q | b |
q3 | b | q | c |
q3 | c | q | d |
q3 | d | q | a |
Bit-Löschung
Q = {q0, q1, q2}, = {0, 1},
= {0,1},
und
siehe Tabelle
Zustand | Eingabe | Folgezustand | Ausgabe |
---|---|---|---|
q0 | 0 | q2 | 0 |
q0 | 1 | q1 | 0 |
q1 | 0 | q2 | 1 |
q1 | 1 | q1 | 1 |
q2 | 0 | q2 | 0 |
q2 | 1 | q1 | 0 |
Quersummenberechnung
Q = {q0, q1, q2, q3}, = {0, 1, 2},
= {0,1, 2, 3, 4}, Beispiele: 01 → 1 22 → 4
Zustand | Eingabe | Folgezustand | Ausgabe |
---|---|---|---|
q0 | 0 | q | |
q0 | 1 | q | |
q0 | 2 | q | |
q1 | 0 | q | |
q1 | 1 | q | |
q1 | 2 | q | |
q2 | 0 | q | |
q2 | 1 | q | |
q2 | 2 | q | |
q3 | 0 | q | |
q3 | 1 | q | |
q3 | 2 | q |
Sätze bilden
Q = {q0, q1, q2, q3, q4),
= {0, 1, 2, 3},
= {verschiedene Worte/Satzfragmente, s. Tabelle und Automat},
Übergänge: s. Tabelle
Zustand | Eingabe | Folgezustand | Ausgabe |
---|---|---|---|
q0 | 0 | q1 | the |
q0 | 1 | q1 | a |
q0 | 2 | q0 | |
q0 | 3 | q0 | |
q1 | 0 | q2 | cat |
q1 | 1 | q2 | child |
q1 | 2 | q2 | newspaper |
q1 | 3 | q0 | and |
q2 | 0 | q3 | ate |
q2 | 1 | q3 | covered |
q2 | 2 | q3 | stood on |
q2 | 3 | q2 | |
q3 | 0 | q4 | the food |
q3 | 1 | q4 | the carpet |
q3 | 2 | q3 | |
q3 | 3 | q3 |
Münzwürfe mit Muster
Q = {q0, q1, q2, q3},
= {0, 1},
= {h, t},
Zustand | Eingabe | Folgezustand | Ausgabe |
---|---|---|---|
q0 | 0 | q1 | h |
q0 | 1 | q2 | t |
q1 | 0 | q3 | h |
q2 | 1 | q3 | t |
q3 | 0 | q0 | h |
q3 | 1 | q0 | t |
Akzeptoren (finite automaton)
- Suche nach der Schatzinsel3)
Q = {q0, q1, q2, q3, q4, q5, q6} „Inseln“,= {A, B}, Endzustand: q4 (nach unserer Nummerierung)
Beispiele für:
Zustand | Eingabe | Folgezustand | Kommentar |
---|---|---|---|
q0 | A | q6 | |
q0 | B | q1 | |
q1 | A | q0 | |
q1 | B | q2 | |
q2 | A | q3 | |
q2 | B | q5 | |
q3 | A | q0 | |
q3 | B | q4 | Schatzinsel erreicht |
q5 | A | q1 | |
q5 | B | q6 | |
q6 | A | q1 | |
q6 | B | q5 |
- Bedingungen für Eingabeworte finden