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.)

Beliebteste Tags

verständnis alternativlösung klausur kellerautomat endlicher-automat grammatik regulärer-ausdruck pumpinglemma turingmaschine tipp zahlendarstellung cmos klausurrelevant bonusklausur komplexität schaltwerk binary-decision-diagram deterministisch assembler schaltnetz sprachen minimierung nichtdeterministisch huffman fehler-in-aufgabe chomsky-normalform anwesenheitsübung rechtslinear heimübung flip-flop cocke-younger-kasami-algorithmus kontextsensitive-grammatik kontextfreie-grammatik huffman-kodierung hauptklausur fehlererkennbarkeit vorlesungsfolien kontextfreie-sprache polynomialzeitreduktion faq gleitkommazahl fehlerkorrigierbarkeit rechtslineare-grammatik dateiorganisation cache darstellung-klausur nachklausur xwizard adressierungsarten lambda mealy konjunktive-normalform pipelining zustände saalübung leeres-wort endliche-automaten ohne-lösungen betriebssystem speicherorganisation moore monotone-grammatik 2-komplement fehler reguläre-sprache hammingzahl monoton lösungsweg pumping-lemma-für-kontextfreie-sprachen kodierung berechenbarkeit klausureinsicht disjunktive-normalform pumping-lemma info-ii bussysteme rechnerarchitektur abzählbarkeit komplexitätsklassen ableitungsbaum vorlesungsaufzeichnung round-robin minimierung-endlicher-automaten chomsky-klassen binärzahl entscheidbar programmiersprachen entscheidbarkeit aufzählbarkeit stern-symbol automaten nukit-fragen bewertung zugriffsarten von-neumann-rechner umformung adressierung mengen binär-subtrahieren organsiation

Kategorien

0 Pluspunkte 0 Minuspunkte
66 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!
in AU-3-4 von uodsh uodsh Eins-Komma-Null-Anwärter(in) (2.3k Punkte)  

2 Antworten

0 Pluspunkte 0 Minuspunkte
 
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.
von ujegu ujegu Tutor(in) (103k Punkte)  
ausgewählt von uodsh uodsh
0 0
Danke das macht Sinn ! :)
0 Pluspunkte 0 Minuspunkte
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.
von ujegu ujegu Tutor(in) (103k Punkte)  
0 0
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?
0 0
Ä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.
...