Informatiker Board | Druckvorschau: Epsilon aus Grammatik (genauer Startregel) entfernen?

Geschrieben von Liquid am 09.02.2017 um 21:30:

Epsilon aus Grammatik (genauer Startregel) entfernen?

Wenn ich eine Grammatik mit dem Produktionen
S -> Epsilon | SS | [S] | (S)

wie kann ich dann das Epsilon entfernen? Ist das nicht ein Sonderfall gewesen oder kann ich das auch so ersetzen?

S -> SS | [S] | (S) | S | [] | ()

oder wäre das nicht gültig?
War da nicht irgendwas mit einem Sonderfall oder würde das so, wie oben beschrieben auch gehen? Ansonsten war das ja glaube ich so, das man eine neue Startregel einführt, die dann auf die alte übergeht oder wie war das?

S' -> Epsilon | S
S -> SS | [S] | (S)

Wären die beiden Sachen äquivalent oder wäre nur das zweite richtig bzw. ist überhaupt eins davon riichtig?

Das Ziel ist eigentlich eine Chomsky-Normalform zu erstellen aber geht das überhaupt mit nur einer Regel oder sollte man da die Grammatik lieber verändern?

Geschrieben von eulerscheZahl am 10.02.2017 um 08:05:

$[latex]S\rightarrow\epsilon[/latex]$ ist zulässig. Für alle anderen Variablen muss das Epsilon natürlich weg.

S -> SS | [S] | (S) | S | [] | ()
hier fehlt ja wieder das Epsilon. S->S macht nicht wirklich Sinn.