Ableitungsbaum aus dem CYK Algo

Neue Frage »

Auf diesen Beitrag antworten »
foogi 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
 
Auf diesen Beitrag antworten »
foogi

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?
Auf diesen Beitrag antworten »
ed209

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 ([latex]w_{1,6}[/latex]) besteht aus B ([latex]w_{1,3}[/latex]) und D ([latex]w_{4,6}[/latex]) usw.

Gruß,
ED
 
Neue Frage »
Antworten »


Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »