deterministischer endlicher Automat (DEA)

Definition

$A=(Q,\Sigma ,q_s,\delta ,F)$

• Q eine endliche Menge von Zuständen ist
• $\Sigma$ ein Eingabealphabet ist
• $q_s\in Q$ der Anfangszustand ist
• $\delta :Q\times \Sigma ⟶Q$ die Übergangsfunktion ist
• $F\in Q$ eine Menge von akzeptierenden Zuständen ist

• NEA zu DEA

• erreichbarer Zustand

• minimal-DEA

• Isomorphie von DEAs

• Entscheidungsprobleme