Compilerbau: Endliche Automaten

Akzeptor	endlicher erkennender Automat

Bestandteile	5-Tupel
	A = (I, Q, δ, q₀, F)

I	Eingabealphabet

Q	Zustandsmenge (nichtleer, endlich)

q₀	Anfangszustand

F	Endzustandsmenge
	F ⊆ Q

δ	Übergangsfunktion
	δ : Q x I → Q

	δ ist im Allgemeinen nur partiell definiert

	deterministischer endlicher Automat

Verallgemeinerung	δ Relation
	δ : Q x I → ℘ Q
oder	δ : Q x I → Set Q

	δ total definiert

	nichtdeterministischer endlicher Automat

akzeptierte Sprache L(A)	L(A) = { w ∈ I^* \| (q₀, w) ⊢^* q, q ∈ F}

(q₀, w) ⊢^* q	der Anfangszustand q₀ wird durch Eingabe von w in den Endzustand q ∈ F überführt.

Zustandsübergang (q₁, c) ⊢ q₂	Von dem Zustand q₁ wird durch Eingabe eines Zeichens c gemäß der Übergangsfunktion δ in den Zustand q₂ gewechselt.

⊢^*	ist eine (auch 0-fache) Wiederholung von ⊢

	bei deterministischen Automaten muss δ für jedes Zeichen aus w definiert sein
	bei nichtdeterministischen Automaten muss es eine Möglichkeit geben, einen Endzustand zu erreichen

	deterministische endliche Automaten erkennen ein Wort w in einer Zeit proportional zu \|w\|

	zu jedem nichtdeterministischen endlichen Automaten gibt es einen gleichwertigen deterministischen endlichen Automaten

?	Was heißt gleichwertiger Automat?

Zustands- Übergangs- Diagramm	grafische Darstellung eines Automaten

Endliche Automaten