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

Colaautomat als Mealy-Automat

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 lambda für die nicht definierte Ausgabefunktion erscheinen.

Formale Beschreibung

Ein endlicher Automat A lässt sich als Sechstupel beschreiben: A ~=~ (Q,~ Sigma,~ Omega,~ delta,~ lambda,~ q_0)1)

Die Symbole stehen dabei im Einzelne für die folgenden Eigenschaften des Automaten:

  • Q: endliche Menge der Zustände, im Beispiel Colaautomat Q = {ungeladen, geladen}
  • Sigma: endliche Menge der Eingaben, im Beispiel Sigma = {1€, Cola ausgeben, Geld zurück}
  • Omega: endliche Menge der Ausgaben, im Beispiel Omega = {1€, Cola}
  • delta:Qx Sigma right Q : Übergangsfunktion, die aus einer Zustands-Eingabekombination den Folgezustand ermittelt, z.B. delta(ungeladen, 1€) = geladen oder delta(geladen, Cola ausgeben) = ungeladen
  • lambda:Qx Sigma right Omega : Ausgabefunktion, die aus einer Zustands-Eingabekombination die eindeutige Ausgabe ermittelt, z.B. lambda(geladen, Cola ausgeben) = Cola
  • q_0~in~ Q: Anfangszustand, wird im Beispiel festgelegt auf q_0= 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

Negierung, 2 Zustände Q = {q0, q1}, Sigma = {0, 1}, Omega = {0,1}

delta(q0, 0) = q1~~ delta(q1,1) = q0~~ delta(q0, 1) = q0~~ delta(q1,0) = q1

lambda({q0|q1}, 0) = 1~~ lambda({q0|q1}, 1) = 0~~ (hier steht | für 'oder')

ZustandEingabeFolgezustandAusgabe
q00q11
q01q00
q10q11
q11q00

Negierungsautomat mit einem Zustand

Negierung Q = {q0}, Sigma = {0, 1}, Omega = {0,1}, delta(q0, {0|1}) = q0, lambda(q0, 0) = 1, lambda(q0, 1) = 0

ZustandEingabeFolgezustandAusgabe
q00q01
q01q00

Zeichenersetzungsautomat

Zeichenersetzung Q = {q0, q1}, Sigma = {0, 1}, Omega = {f,w}, Umwandlungsregeln: 0 → f 1 → w

ZustandEingabeFolgezustandAusgabe
q00q0f
q01q1w
q10q0f
q11q1w

Zyklische Zeichenvertauschung

Zeichenvertauschung

Q = {q0, q1, q2, q3}, Sigma = {a, b, c, d}, Omega = {a, b, c, d}, Umwandlungsregeln: a → b, b → c, c → d, d → a

ZustandEingabeFolgezustandAusgabe
q0aqb
q0bqc
q0cqd
q0dqa
q1aqb
q1bqc
q1cqd
q1dqa
q2aqb
q2bqc
q2cqd
q2dqa
q3aqb
q3bqc
q3cqd
q3dqa

Bit-Löschung

Bit-Löschung

Q = {q0, q1, q2}, Sigma = {0, 1}, Omega = {0,1},

delta(Zustand, Eingabe) -> Folgezustand und lambda(Zustand, Eingabe) -> Ausgabe siehe Tabelle

ZustandEingabeFolgezustandAusgabe
q00q20
q01q10
q10q21
q11q11
q20q20
q21q10

Quersummenberechnung

 Quersummenberechnung

Q = {q0, q1, q2, q3}, Sigma = {0, 1, 2}, Omega = {0,1, 2, 3, 4}, Beispiele: 01 → 1 22 → 4

ZustandEingabeFolgezustandAusgabe
q00q
q01q
q02q
q10q
q11q
q12q
q20q
q21q
q22q
q30q
q31q
q32q

Sätze bilden

Sätze bilden Q = {q0, q1, q2, q3, q4), Sigma = {0, 1, 2, 3},

Omega = {verschiedene Worte/Satzfragmente, s. Tabelle und Automat}, Übergänge: s. Tabelle

ZustandEingabeFolgezustandAusgabe
q00q1the
q01q1a
q02q0
q03q0
q10q2cat
q11q2child
q12q2newspaper
q13q0and
q20q3ate
q21q3covered
q22q3stood on
q23q2
q30q4the food
q31q4the carpet
q32q3
q33q3

Münzwürfe mit Muster

Münzwurfautomat Q = {q0, q1, q2, q3}, Sigma = {0, 1}, Omega = {h, t},

delta(q0,0) = q1,~~~ delta(q0,1) = q2,~~~ delta(q1,0) = delta(q2,1) = q3,~~~ delta(q3,0) = delta(q3,1) = q0

lambda(q0,0) = h,~~~ lambda(q0,1) = t,~~~ lambda(q1,0) = h,~~~ lambda(q3,1) = t,~~~ lambda(q3,0) = h,~~~ lambda(q3,1) = t

ZustandEingabeFolgezustandAusgabe
q00q1h
q01q2t
q10q3h
q21q3t
q30q0h
q31q0t

Akzeptoren (finite automaton)

  • Suche nach der Schatzinsel3)
    Q = {q0, q1, q2, q3, q4, q5, q6} „Inseln“, Sigma = {A, B}, Endzustand: q4 (nach unserer Nummerierung)
    Beispiele für delta: delta(q0, A) = q6 delta(q0,B) = q1

Pirateninseln

ZustandEingabeFolgezustandKommentar
q0Aq6
q0Bq1
q1Aq0
q1Bq2
q2Aq3
q2Bq5
q3Aq0
q3Bq4 Schatzinsel erreicht
q5Aq1
q5Bq6
q6Aq1
q6Bq5
  • Alternative Schatzinselkarte
    Alternative Schatzinselkarte
  • Bedingungen für Eingabeworte finden

Bedingungen finden, 1 Bedingungen finden, 2 Bedingungen finden, 3

1)
Schriek, S. 111
2)
alle Bespiele aus Schriek, Informatik mit Java III, S. 113f
schule/if/q1q2/einstiegautomaten.txt · Zuletzt geändert: 2018/05/31 20:06 von ahrens
CC Attribution-Noncommercial-Share Alike 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0