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!
 

 

Idee der Grammatik?

+1 Punkt
41 Aufrufe

hallo ,

könnte mir jemand die allgemeine Idee hinter dieser Grammatik erklären? Ich verstehe nicht, wie ich damit sicherstelle dass die Anzahl an a's immer verdoppelt wird.

Danke!

 

Gefragt 29, Sep 2015 in 2012-N-04 von uafjv uafjv Tutor(in) (167,990 Punkte)  

Eine Antwort

–1 Punkt

Die allgemeine Idee wird in den Hinweisen formuliert. Ich mache mal ein Beispiel mit der allgemeinen (korrigierten, s.o.) Grammatik, die Ableitung der Terminalworte lasse ich der Einfachheit halber weg:

S -> VAH  (hat 1 A bzw. a.) -> VABH ->  VBAAH -> VAAH  (hat  2 A bzw. a) -> VAABH -> VABAAH -> VBAAAAH -> VAAAAH (4 A/a) usw.

Man sieht, dass man das B nur direkt vor dem H erzeugen kann und nur direkt hinter dem V wieder los wird, d.h. jedes erzeugte B muss einmal komplett durch die As geschoben werden. Das geht nur mit der Regel AB->BAA. Dadurch bekommt man für jedes A, an dem man das B vorbeischiebt, ein neues A hinzu. Insgesamt verdoppelt sich also die Anzahl der As mit jedem B, dass von hinten nach vorne wandert.

Tobias (Tutor)

 

Beantwortet 29, Sep 2015 von uafjv uafjv Tutor(in) (167,990 Punkte)  
...