Revision [6596]

This is an old revision of AtfsProduktionen made by ToBo on 2008-11-21 00:30:30.

 

Produktionen und Grammatik formaler Sprachen


(SkriptAtfsEckNr2, S. 47)

1. Was sind Produktionen?


G sein die Grammatik einer formalen Sprache

image

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.


2. Produktionen


Produktionen sind Ersetzungsregeln.

A → ε Reduktion
A → t Termination
A → tB Expansion
A → BC Expansion
A → CD Doppelte Substitution


Beispiel


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

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


3. Sprache und Grammatik


L ist eine formale Sprache eine Sprache mit der Grammatik G

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


4. 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.








Siehe auch
Valid XHTML :: Valid CSS: :: Powered by WikkaWiki