Deterministischer Endlicher Automat (DEA)

Deterministischer¹ Endlicher² Automat (DEA)

DEA sind als Pentupel (5-Tupel) definiert:

Z	Menge aller Zustände
E	Menge aller Eingabezeichen (Eingabealphabet)
$\sigma :Z\times E\to Z$	Übergnagsfunktion
$Z_0\in Z$	Startzustand
$F\le Z$	Menge der Endzustand (Teilmenge der aller Zustände)

Kennzeichnung:

• Startzustand:

stateDiagram-v2
	[*] --> ""

stateDiagram-v2
	Zustand --> [*]

Dargestellt wird ein DEA in einem Übergangsgraph:

Hausaufgabe

stateDiagram-v2
	
	z0
	note left of z0 
		Start- und Endzustand
	end note
	z0 --> z1 : 1
	z1 --> z0 : 1
	
	z1 --> z3 : 0
	z3 --> z1 : 0

	z2 --> z3 : 1
	z3 --> z2 : 1
	
	z2 --> z0 : 0
	z0 --> z2 : 0

Link zum Original

Zustandstabelle

Zustandstabelle

Eine andere Darstellungsmethode für deterministische endliche Automaten ist eine Zustandstabelle / Übergangstabelle.

Ausgangszustand	0	1
$z_0$	$z_2$	$z_1$
$z_1$	$z_3$	$z_0$
$z_2$	$z_0$	$z_3$
$z_3$	$z_2$	$z_1$

Link zum Original

Footnotes

1. eindeutig bestimmt (für die gleiche Eingabe wird immer der gleiche Übergang gewählt) ↩

2. endliche Anzahl von Zuständen ↩