wenn ich eine CNF Normalform habe, und dise dann kann man ja mit dem CYK Algorithmus bestimmen, ob das Wort in der Sprache ist oder nicht. Wenn das Wort nun in der Sprache ist, so ist ja das letzte Nichtterminal ein S, bzw das Startsymbol. Soweit so gut, kann ich nun systematisch den Ableitungsbaum erstellen, oder geht das nur mit rumprobieren?
also ich hab folgendes Wort zum ableiten:
abbaba
die Grammatik ist folgende:
S--> AB|BA|AC|BD
A--> a| BE
B--> b| AF
C--> BS
D--> AS
E--> AA
F--> BB
so, das Wort ist in der Sprache, weil ich ja als letztes auf S komme,
(1,6).
wie komme ich nun auf den Ableitungsbaum?
code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
X 1 2 3 4 5 6
1 A S B S C S
2 B F C
3 B S C S
4 A S D
5 B S
6 A
Man muss sich nur beim ausfüllen der Tabelle notieren, welche Produktionen man genutzt hat, notieren, dass man die Regel S -> BD angewandt hat, um aus den Feldern (1,3) und (4,6) auf das S in (1,6) zu schließen.
Gibt es nun eine Möglichkeit, um auf die Sprache zu kommen?
also was wäre hier L(G)?
und kann man eine Aussage darüber treffen, ob L deterministisch kontextfrei ist? wenn ja anhand von was?
Du könntest dir zu jedem Eintrag in der Tabelle abspeichern wie du dazu gekommen bist, aber dadurch verbessert sich dein Algorithmus auch nicht wesentlich, als wenn du "rumprobieren" würdest.
Wenn du die Tabelle hast, kannst du ja sehr schnell sehen mit welchen beiden Einträgen du von deinem Start-S weiterkommst.
