Kontextfreie Grammatik |
03.02.2011, 00:53 | Auf diesen Beitrag antworten » |
levie | 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 |
|
|