Revision [5778]
This is an old revision of AtfsProduktionen made by ToBo on 2008-10-25 14:47:38.
Produktionen in den Automatentheorie
1. Was sind Produktionen?
Produktionen sind Ersetzungsregeln.
G sein die Grammatik einer formalen Sprache
G = (N, T, S, P)
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)+ × (N ∪ T)* und heißt die Menge der Produktionen.
Beispiel
Schritte:
- <number> := <digit>{<digit>}
- <digit> := 1
- <digit> := 5
<number> → <digit><digit> → 1<digit> → 15
Sprache und Grammatik
L ist eine formale Sprache eine Sprache mit der Grammatik G
L(G) = {x ∈ T* | S ⇒ x }
2. Chomsky-Hierarchie
S. 49
Allgemeine Grammatiken (Typ 0)
A → ε Reduktion
A → t Termination
A → tB Expansion
A → BC Expansion
A → CD Doppelte Substitution
Nichtverkürzte Grammatiken (Typ 1)
kontextsensitiv
A → t Termination
A → BC Expansion
A → CD Doppelte Substitution
Kontextfreie Grammatiken (Typ 2)
A → t Termination
A → BC Expansion
(rechts-)lineare Grammatiken (Typ 3)
A → t Termination
A → tB Expansion
Wobei A,B,C,D ∈ N und t ∈ T ist.