---

Geschrieben von levie am 03.02.2011 um 00:53:

  Kontextfreie Grammatik

Hi,
ich soll einen Aufgabe lösen und finde leider überhaupt keinen ansatz ich hoffe ihr könnt mir helfen....

Sei G=(N,T,P,S) eine kontextfreie Grammatik. Für i € N sei die Menge Mi wie folgt Definiert:
M0= die leere Menge
Mi+1= Mi U {A€N | (A::=u) € P, u€(Mi U T)*}
zeige die folgenden Behauptungen:

(a) Es existiert ein k€N mit Mk=Mk+1
(b) Für ein derartiges k gilt: Mk=Mk+j für alle j€N
*
(c) Für alle i€N gilt: A€Mi impliziert A----->a für ein w€T*
p
i
(d) für alle i€N gilt : A------>w mit w€T* impliziert A€Mk
p
Beweis bei (d) mit dem Kontextfreiheitslemma

€ = Element
N = die menge der Natürlichen Zahlen

Vielen Dank schon mal