Geschrieben von Theo_info am 13.01.2018 um 16:05:
Grammatik auf Chomsky Normalform bringen
Hallo,
Ich habe eine Grammatik mit diesen Produktionsregeln:
S -> AB|BAB|Ba
A -> BA|a
B -> aa|aAB|ABa|ABAB|b
1.) Terminale ersetzen:
S -> AB|BAB|BX
A -> BA|a
B -> XX|XAB|ABX|ABAB|b
X -> a
2.) Lange Blöcke eliminieren:
S -> AB|BC|BX
A -> BA|a
B -> XX|XC|AD|AE|b
C -> AB
D -> BX
E -> BC
X -> a
Kann das noch irgendwie reduziert werden, oder bin ich jetzt bereits fertig?
Danke für eure Hilfe!
