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

Alternativer Lösungsvorschlag

+1 Punkt
57 Aufrufe
Wäre folgende Grammatik ebenfalls korrekt?

S→   abc | aAB
A→   aAB
AB→ cbA
cb→  bc
cA→  c
Gefragt 8, Jan 2016 in MON-AD von updrq updrq Tutor(in) (103,620 Punkte)  

Eine Antwort

0 Punkte

Hey updrq,

deine Grammatik ist leider nicht korrekt. Zum einen ist deine Grammatik nicht monoton, was in der Aufgabenstellung gefordert war.
Eine Grammatik ist dann monoton, wenn für alle Regeln die länge der Symbolkette auf der rechten Seite mindestens so groß ist wie die Länge der Symbolkette auf der linken Seite. Deine letzte Regel verstößt dagegen.

Aber ungeachtet davon, könnte mit einer Gramatik mit deiner Regelmenge Wörter produziert werden, die nicht zur Sprache gehören: Ein Beispiel
S ⇒aABaaABB⇒aacbAB⇒aacbcbA⇒aacbbcA⇒aacbbc


Viele Grüße
Ashvin

Beantwortet 8, Jan 2016 von uxdiu uxdiu Tutor(in) (101,710 Punkte)  
...