| Der letzte Beitrag |
| GastUser |
Kontextfreie Grammatik reduzieren
Hi zusammen,
ich bearbeite im Rahmen meines Studiums gerade eine Übungsaufgabe (unbenotet, ich will hier also nicht meine Arbeit von anderen erledigen lassen 
).
In der Aufgabe geht es darum eine kontextfreie Grammatik zu reduzieren.
Die Beispiele aus dem Studienheft konnte ich eigentlich nachvollziehen und ich dachte auch ich hätte es verstanden, aber offensichtlich habe ich mich da getäuscht...
Also, die Grammatik ist folgende:
kfG G = (N, T, P, s) mit
N = {A, W, N, F, R, G},
T = {a, r, b, y, g, p, 1, 2, l, s, h},
P = { A -> aN,
W -> FRGN,
N -> W | epsilon,
F -> r | b | y | g | p,
R -> 1 | 2,
G -> l | s | h},
s = A
Nun steht in meinem Studienheft, dass man zuerst die unnützen Nonterminale wegstreichen soll. Das sind alle, die nicht terminieren.
Dafür gibt es folgende Vorgaben:
- Das Startsymbol, in meinem Fall das Nonterminal A, darf nicht gestrichen werden
Und zum Filtern der unnützen Nonterminale iteriert man über die zwingend notwendigen Terminale mit folgenden Formeln:
- M(1) = {X | X teil von N und (X -> alpha) teil von P mit alpha teil von T+}
- M(i+1) = M(i) U {X | X teil von N und (X-> alpha) teil von P mit alpha teil von (M(i) U T)+} für i >= 1
Wenn ich die Regeln auf die obenstehende Grammatik anwende habe ich folgende Nonterminale:
M(1) = {F,G,R}
M(2) = {F,G,R,W}
M(3) = {F,G,R,W,N}
M(4) = {F,G,R,W,N,A} = M(5)
Somit habe ich rein gar nichts reduziert. Kann das sein?
Ich wäre sehr dankbar, wenn jemand mit Ahnung von der Reduzierung mir weiterhelfen kann.. 
Vielen Dank schon mal! |
|
|
