Automaten
deterministischer endlicher Automat (DEA)
nichtdeterministischer Kellerautomat
K = (Q, Σ, K, δ, s, #, F) (7-Tupel)
epsilon-Übergänge
Compiler
Transformationen
nichtdeterministischer endlicher Automat (NEA)
Grammatiken
Sprachen
reguläre Grammatik
Chomsky-Hierarchie
G = ( N, T, S, P) (4-Tupel)
G = (Q, s, Σ, F, δ) (5-Tupel)
s := Startzustand
𝚺 := Eingabealphabet
F := Menge der Endzustände
𝛅: QxF→Q^n := Übergangsrelation
Q := Zustandsmenge
G = (Q, s, Σ, F, δ) (5-Tupel)
Q := Zustandsmenge
s := Startzustand
𝚺 := Eingabealphabet
F := Menge der Endzustände
𝛅: QxF→Q := Übergangsfunktion
Typ-2: Kontextfreie Sprachen
rechtsregulär
Typ1: Kontextsensitive Sprachen
Typ-0: Beliebige Sprachen
N := Nicht-terminalsymbole
T := Terminalsymbole
S := Startsymbol
P := Menge der Produktionen
Scanner
Parser
Lexer
NEA in DEA (Potenzmengenkonstruktion)
DEA in reg. Grammatik
DEA in reg. Ausdruck
Kellerautomat in kontextfreie Grammatik
Typ-3: Reguläre Sprachen
linksregulär
kontextfreie Grammatik
Darstellungsformen
Mengendarstellung
(erweiterter) regulärer Ausdruck
L=
L = {w|w ist ein Palindrom}
a*(c|d)b*