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!
 

 

andere "CB -> BC"-Umstellung auch möglich?

–1 Punkt
30 Aufrufe

Ist folgende Umstellung von CB -> BC legitim für kontextfreie Sprachen:

CB -> BB

BB -> BC

somit wäre die Hilfvariable in der Musterlösung überflüssig oder ?

 

Gefragt 25, Sep 2015 in 2013-H-02 von uafjv uafjv Tutor(in) (167,840 Punkte)  

Eine Antwort

0 Punkte

Hallo,

mit den zwei Regeln könntest du Wörter mit der Grammatik erzeugen, die nicht in der Sprache sind.

Z.B. wäre die Ableitungsfolge

S -> aSBBCCC -> aabbCCCBBCCC -> aabbCCCBCCCC - >...

möglich, du hast dann also nicht mehr nur die reine Umsortierung sondern kannst auch "b's in c's" umwandeln (oder "c's in b's" wenn du deine erste Regel analog anwendest).

Viele Grüße

Christiane (Tutorin)

 

Beantwortet 25, Sep 2015 von uafjv uafjv Tutor(in) (167,840 Punkte)  
...