=====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. oder 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. ==a==Produktionen==a== Produktionen sind Ersetzungsregeln. A → ε Reduktion A → t Termination A → tB Expansion A → BC Expansion AB → CD Doppelte Substitution ===Beispiel=== Schritte: ~1) := {} ~1) := 1 ~1) := 5 → → 1 → 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}}