Hallo,
Ich habe eine Frage zum CYK-Algorithmus. Ich weiss nicht wie geläufig der hier ist. Darin geht es darum zu testen ob ein bestimmtes Wort in einer Sprache liegt.
Dazu habe ich folgende Sprache:
S -> AB|CA
A -> BB|b
B -> CA|a
C -> AC|a
und folgendes Wort: aabbabaaa
Meine Tabelle sieht so aus bisher:
|---+-----+-----+-----+-----+-----+-------+-------+-----+-----|
| | a | a | b | b | a | b | a | a | a |
| a | B,C | | | | | | | | |
| a | A | B,C | | | | | | | |
| b | A | S,B | A | | | | | | |
| b | X | X | X | A | | | | | |
| a | C | X | C | S,C | B,C | | | | |
| b | | A | S,B | S,B | S,B | A | | | |
| a | | | A | A | A | S,C | B,C | | |
| a | | | | S,C | S,C | X | A | B,C | |
| a | | | | | A | B,S,C | B,S,C | A | B,C |
|---+-----+-----+-----+-----+-----+-------+-------+-----+-----|
Die Lösung sieht so aus:
|- |a |a |b |b |a |b |a |a |a
|a |{B,C} |- |- |- |- |- |- |- |-
|a |{A} |{B,C} |- |- |- |- |- |- |-
|b |{A} |{S,B} |{A} |- |- |- |- |- |-
|b |- |- |- |{A} |- |- |- |- |-
|a |{C} |- |{C} |{S,C} |{B,C} |- |- |- |-
|b |{S,B} |{A} |{S,B} |{S,B} |{S,B} |{A} |- |- |-
|a |{A} |{S,B,C} |{A} |{A} |{A} |{S,C} |{B,C} |- |-
|a |{S,B,C} |{A} |{C,S} |{C,S} |{S,C} |- |{A} |{B,C} |-
|a |{A} |{S,B,C} |{A} |{A} |{A} |{S,C,B} |{S,B,C} |{A} |{B,C}
Kann mir jemand sagen wieso links neben dem A unterste Zeile ein weiteres A kommt? Im Moment folge ich dem Algorithmus so in dem ich immer das oberste mit dem Rechten vergleiche und das Unterste mit dem was in der Zeile ganz links steht. Wenn ich die Letzte zeile betrachte komme ich auf folgende Kombinationen:
CA,SA,CB,CC,SB,SC
Keine dieser Kombinationen ergibt ein A. Also wieso kommt da ein A hin?!