Blatt 3 #2

[Thomas]

Wollte mal meine Chomsky-Normalform-Grammatik zum vergleichen reinstellen, weil ich da absolut kein plan hab, ob die richtig is.
und zwar hab ich als startsymbol S und meine produktionen sehen wie folt aus:

PRIME_BBCODE_SPOILER_SHOW PRIME_BBCODE_SPOILER: auf Anzeigen klicken

S --> epsilon
S --> a
S --> b
S --> AA
S --> BB
S --> AY
S --> BZ
Y --> XA
Z --> XB
X --> a
X --> b
X --> AA
X --> BB
X --> AY
X --> BZ
A --> a
B --> b

[SLS]

Ich habe genau das gleiche Ergebnis
Ich glaube, es würde aber auch gespiegelt funktionieren. Folgendes sollte also auch richtig sein:

PRIME_BBCODE_SPOILER_SHOW PRIME_BBCODE_SPOILER: auf Anzeigen klicken

S -> YA | ZB | AA | BB | a | b | epsilon
Y -> AX
Z -> BX
X -> YA | ZB | AA | BB | a | b
A -> a
B -> b

Allerdings ergibt sich dann natürlicherweise eine gespiegelte Pyramide bei der Anwendung vom CYK-Algorithmus.