(2) Eliminiere reine Umbenennungen

Question

Hallo zusammen,

diese Regelmenge war gegeben:

P = {

S -> A | A + S,

A -> x | aAa | bAb }

Wenn ich S -> A als Umbenennung ansehe,

kann ich dann nicht folgende verkürzte Regelmenge als äquivalent ansehen?

P' = {

S -> x | aSa | bSb | S+S

}

Vielen Dank!

Answer 1

Hi,

da habe ich vorhin nicht genau hingeguckt.

Leider ist die von Ihnen angegebene Regelmenge doch nicht äquivalent, da Sie A ja vollständig abschaffen.
Das führt aber zu Problemen, denn:

Durch Ihre Regelmenge P' kann man das Wort ax + xa erzeugen.
(S -> aSa ->aS+Sa ->ax+SA->ax+ax)

Diese Worte sind jedoch nicht in der Sprache enthalten, die durch die Grammatik mit P erzeugt wird.

Comments

Danke das macht Sinn ! :)

Answer 2

Hallo,

fast richtig! Die von Ihnen angegebene Regelmenge ists äquivalent, aber:

Die Regel S->A + S ist keine reine Umbenennung und darf in diesem Arbeitsschritt nicht angefasst werden.

P'= {

S -> x |aAa | bAb | A+S
A -> x |aAa| bAb

}

ist eine äquivalente Regelmenge zu P, die keine reinen Umbenennungen enthält.

Comments

Wenn ich das richtig verstehe heißt das, dass meine Regelmenge äquivalent und meines Erachtens auch einfacher als die Musterlösung ist, nur streng nach dem Algorithmus in Schritt 2 eben nur Umbenunnungen eliminiert werden dürfen. Ist das so korrekt und wäre die Lösung dadurch falsch?

---

Äquivalenz ist hier leider nicht gegeben. Dazu mehr in meiner zweiten Antwort.
Prinzipiell gilt in der Klausur: Wenn ein Algorithmus erfordert ist, sollte dieser auch nachvollziehbar durchlaufen werden.
Für eine richtige Lösung ohne Algorithmus gibt es sonst evtl. nur Teilpunkte.