Sichtweisen

Automat

Endlisch: automaton/automata, finite state machine, Finite Automaton FA, DFA (Deterministic), NFA (Non-Determinstic)

• endliche Anzahl an Zuständen

  Anfangszustand (nur 1)

  Endzustände (optional)

• endliche Symbolfolgen als Eingabe

• Übergänge zwischen Zuständen

• Eingaben / Ausgaben / Aktionen

  während Zustandsübergang oder im Zustand selbst

  Eingaben XOR Ausgaben

• kann mit / ohne $\varepsilon$ -Übergängen sein

Transducer

• mit Ein- und Ausgang

• kann auch unendliche Symbolfolgen verarbeiten

Unterarten

1. Deterministisch DEA

   momentaner Zustand $\times$ nächste Eingabe $\mapsto$ Folgezustand (eindeutig)

   Verglichen zu NEAs

   • Effizientere Abarbeitung, kein Backtracking

2. Nichtdeterministisch NEA

   momentaner Zustand $\times$ nächste Eingabe $\mapsto$ { Folgezustände }

   Verglichen zu DEAs

   • Flexibler

   • Leerwort erlaubt

   • Weniger Zustände

   • leichter zu konstruieren

3. Mealy-Automat (Transducer)

   Deterministisch

   keine Endzustände

   Ausgabe mit Eingabe verknüpft

   Die Ausgabe erfolgt bei Zustandswechsel

4. Moore-Automat (Transducer)

   Deterministisch

   keine Endzustände

   Ausgabe mit Zustand verknüpft

   Die Ausgabe erfolgt durch momentanen Zustand

5. Büchi-Automat

   Wie endlicher Automat aber unendliche Symbolfolgen

6. ...

   zb Verallgemeinerter endlicher Automat, Muller-Automat, Rabin-Automat, Baumautomaten, ...

Allgemein gilt:

1. DEAs und NEAs besitzen dieselbe Ausdrucksstärke.

   Jede DEA ist ein NEA.

   Jede NEA lässt sich Determinisieren.

2. Moore und Mealy besitzen dieselbe Ausdrucksstärke.

   beide schwächer als Transducer.

   Moore haben in der Regel mehr Zustände als Mealy.

3. Nichtdeterministische Büchli sind ausdrucksstärker als deterministische