Formale Grammatik
Viertupel G = (N,Σ,P,S)
N Nichtterminalsysmbole, endlich
T Terminalsymbole, endlich, nicht-leer
P Produktionsregeln, endlich, nicht-leer;
Form (p,q) Element N ∪ T,
p mind. ein Nichtterminalsymbol
S Startsymbol, Axiom, Element N
N disjunkt T: kein Symbol in N und in T
Ableitung
x ∈ (N ∪ T) und (p, q) ∈ P
mit x = x’p“, x‘, x“ ∈ (N ∪ T)*
x → (p, q)y bzw x → y mit y = x’qx‘
Erzeugte Sprache
Menge aller gültigen Wörter, die aus S ableitbar sind
Beispiel
N = {S1}
T = {a,b} -> L = {a,b} *
P = {(S1, E), (S1,aS1b)}
habe ich S1 kann ich dies ersetzen durch E oder aS1b
S1 -> aS1b -> aaS1bb -> aaaS1bbb -> a³Eb³ = a³b³
aaS1bb = a²S1b²
aaaS1bbb = a³S1b³
ein gültiges Wort der durch die Grammatik erzeugten Sprache
S1 -> E = a0b0
S1 -> aS1b -> ab = a1b1
-> L (G1) = { w|w = anbn, n ∈ N0 }