Wiki source for AtfsProduktionen
=====Produktionen und Grammatik formaler Sprachen=====
(SkriptAtfsEckNr2, S. 47)
==a==Was sind Produktionen?==a==
G sein die Grammatik einer formalen Sprache
{{image url="images/AtfsGrammatik.png"}}
N: Alphabet der nichtterminalen Symbole, Platzhalter, z.B. <digit> oder <number>
T: Alphabet der terminalen Symbole mit N ∩ T = ∅, z.B. 1 oder 'p'
S: Startsymbol mit S ∈ N
P: Eine endliche Teilmenge von (N ∪ T)""<sup>+</sup>"" × (N ∪ T)* und heißt die Menge der Produktionen.
==a==Produktionen==a==
Produktionen sind Ersetzungsregeln.
A → ε Reduktion
A → t Termination
A → tB Expansion
A → BC Expansion
AB → CD Doppelte Substitution
===Beispiel===
Schritte:
~1) <number> := <digit>{<digit>}
~1) <digit> := 1
~1) <digit> := 5
<number> → <digit><digit> → 1<digit> → 15
==a==Grammatik Typ==a==
[[ChomskyHierarchie Chomsky-Hierarchie]]
==a==Sprache und Grammatik==a==
L ist eine formale Sprache eine Sprache mit der Grammatik G
L(G) = {x ∈ T* | S ⇒ x }
----
Siehe auch {{backlinks}}
(SkriptAtfsEckNr2, S. 47)
==a==Was sind Produktionen?==a==
G sein die Grammatik einer formalen Sprache
{{image url="images/AtfsGrammatik.png"}}
N: Alphabet der nichtterminalen Symbole, Platzhalter, z.B. <digit> oder <number>
T: Alphabet der terminalen Symbole mit N ∩ T = ∅, z.B. 1 oder 'p'
S: Startsymbol mit S ∈ N
P: Eine endliche Teilmenge von (N ∪ T)""<sup>+</sup>"" × (N ∪ T)* und heißt die Menge der Produktionen.
==a==Produktionen==a==
Produktionen sind Ersetzungsregeln.
A → ε Reduktion
A → t Termination
A → tB Expansion
A → BC Expansion
AB → CD Doppelte Substitution
===Beispiel===
Schritte:
~1) <number> := <digit>{<digit>}
~1) <digit> := 1
~1) <digit> := 5
<number> → <digit><digit> → 1<digit> → 15
==a==Grammatik Typ==a==
[[ChomskyHierarchie Chomsky-Hierarchie]]
==a==Sprache und Grammatik==a==
L ist eine formale Sprache eine Sprache mit der Grammatik G
L(G) = {x ∈ T* | S ⇒ x }
----
Siehe auch {{backlinks}}