Informatik

Was ist ein deterministischer endlicher Automat?

Ein DFA ist ein Tupel (Q,Σ,δ,q0,F)(Q,\Sigma,\delta,q_0,F) mit endlicher Zustandsmenge QQ, Alphabet Σ\Sigma, Übergangsfunktion δ:Q×Σ→Q\delta:Q\times\Sigma\to Q, Startzustand q0q_0 und Endzuständen FF.

Deterministisch: Für Zustand und Eingabesymbol gibt es genau einen Folgezustand.

Beispiel

DFA für Binärwörter, die auf 11 enden:

start q0 q0 start->q0 q0->q0 0 q1 q1 q0->q1 1 q1->q0 0 q1->q1 1