Revision [5767]

This is an old revision of AtfsProduktionen made by ToBo on 2008-10-25 12:57:09.

 

Produktionen in den Automatentheorie


Produktionen sind Ersetzungsregeln.


G = (N, T, S, P)

N: Alphabet der nichtterminalen Symbole, z.B. <digit>
T: Alphabet der terminalen Symbole mit N ∩ T = ∅, z.B. 1
S: Startsymbol mit S ∈ N
P: Eine endliche Teilmenge von (N ∪ T)+ × (N ∪ T)* und heißt die Menge der Produktionen.


Beispiel 1


Schritte:
  1. <number> := <digit>{<digit>}
  2. <digit> := 1
  3. <digit> := 5

<number> → <digit><digit> → 1<digit> → 15




L(G) = {x ∈ T* | S ⇒ x }

Chomsky-Hierarchie (Typ 0 bis Typ 3) 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.




Siehe auch

Valid XHTML :: Valid CSS: :: Powered by WikkaWiki