Theoretische und technische Informatik - ganz praktisch
Herzlich willkommen auf der Question/Answer-Plattform zu Grundlagen der Informatik II. Wir wünschen Ihnen viel Spaß beim Lernen und Diskutieren!
Loggen Sie sich mit Ihrem KIT-Account (u...) ein, um loszulegen!
Beachten Sie auch diese Informationen zum Schnelleinstieg.
(Nicht-KIT-Studierende beachten bitte diese Informationen.)

Schöne Ferien!
 

 

(2) Eliminiere reine Umbenennungen

0 Punkte
54 Aufrufe
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!
Gefragt 2, Feb 2017 in AU-3-4 von uodsh uodsh Eins-Komma-Null-Anwärter(in) (2,280 Punkte)  

2 Antworten

0 Punkte
 
Beste Antwort
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.
Beantwortet 2, Feb 2017 von ujegu ujegu Tutor(in) (102,600 Punkte)  
ausgewählt 2, Feb 2017 von uodsh uodsh
Danke das macht Sinn ! :)
0 Punkte
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.
Beantwortet 2, Feb 2017 von ujegu ujegu Tutor(in) (102,600 Punkte)  
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.
...