---

Geschrieben von foogi am 09.02.2007 um 12:09:

  Ableitungsbaum aus dem CYK Algo

hallo,

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

EDIT: Code-Tags zugefügt -- ED

---

Geschrieben von foogi am 10.02.2007 um 17:39:

 

ok wie ich den Baum erstelle weiß ich nun:

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?

---

Geschrieben von ed209 am 10.02.2007 um 17:44:

 

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.

S () besteht aus B () und D () usw.

Gruß,
ED