Was ist ein endlicher deterministischer Automat?

Ein endlicher deterministischer Automat(DEA) hat eine endliche Anzahl an Zuständen, von welchen er einen immer als aktuellen Zustand hat. Mit hilfe von Übergängen kann er durch verschienen Eingaben seinen Zustand wechseln. Dabei hat ein Zustand einen Eindeutigen zustandswechsel bei einer Eingabe, es sei denn diese Eingabe führt in eine Senke. Bei der Eingabe ist jedes Element teil des Alphabetes und die Eingabe als ganzes ist ein Wort. Wenn nach Ende der Eingabe der Automat einen Endzustand erreicht hat, dann akzeptiert der Automat dieses Wort.

Formale Definition

Die definision für den oben genannten Automaten wäre die folgende:

Der Automat wird über einen Fünf-Tupel definiert.

A = (Q, Σ, δ, q~0~, F)

Beispiel

Annahme: Alle nicht aufgeführten Übergänge führen in eine "Senke".

• Q = {q0, q1, q2}
• δ = {a, b}
• F = {q2}
• δ :

Indeterministischer Automat

Ein deterministischer Automat, wie oben erwähnt hat einen klaren Zustandsübergang von Zustand zu Zustand. Es gibt allerdings auch indeterministische Automaten (IEA), welche für einem Zustand mehrere Eingaben in verschiedene Übergänge erlaubt. Bei diesem ist der genaue Pfad, den der Automat nimmt nicht Eindeutig, da der Automat mehrere Pfade gleichzeitig verfolgt. Ein Automat akzeptiert hierbei ein Wort, wenn es in irgendeinem Fall zu einem akzeptierten Endzustand führt. Ein Beispiel für einen indeterministische Automaten ist gleich bei der Umwandlung zu sehen.

IDA zu DEA umwandeln

Man kann allerdings immer jeden Indeterministischen Automat in einen deterministischen Automaten umwandeln. Dabei fängt man mit einer Tabelle mit allen Übergängen des IDA an. Dabei gibt es allerdings nur eine Zelle pro Zustand/Eingabe Kombination und mehrere Zustände werden in einen neuen Zustand zusammengefasst. Besonders gut ist die im Beispiel unten sichtbar. Danach werden die kombinierten Übergänge auch verfolgt und deren Folgezustände zusammengefasst. Dies wird solange gemacht, bis alle Übergänge notiert sind. Danach kann man Duplikate entfernen. Dies geschieht, wenn die Zeile von Zustand in einer Anderen vollständig enthalten ist und beide Zeilen entweder Endzustand sind oder nicht. Beide müssen dabei die Eigenschaft Endzustand (ja/nein) gleich haben.

Beispiel

1. Tabelle mit allen initialen Übergängen

2. Tabelle mit ALLEN Übergängen

(q₁, q₂, q₃, q₄ werden nicht mehr aufgenommen, da diese nicht mehr von q₀/Startzustand erreichbar sind und damit irrelevant sind)

3. Duplikate entfernen und umbenennen

Da q₀₁₂₄ und q₀₂₃₄ beide Endzustände sind und die gleichen Übergänge haben, kann man diese auch zusammenfassen. So wird man dann eine Zeile los. Man kann allerdings nicht auch noch q₀₁₃ mit-löschen, da dieser kein Endzustand ist und damit nicht identisch ist.

4. Fertig

Die einzelnen Zustände kann man nun wieder umbenennen und den deterministischen Graphen wieder zeichnen.