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

Konvention bei Produktionen

0 Punkte
22 Aufrufe

Gibt es eine Konvention, dass ich bei der Produktion nur ein Terminalsymbol pro Schritt verwenden darf?

Wäre sonst nicht:

P={S -> 0A | 1100A

      A -> S |  λ}

einfacher?

Vielen Dank im Vorraus

Gefragt 22, Okt 2014 in REC-AC von utdbu utdbu Tutor(in) (106,580 Punkte)  

Eine Antwort

0 Punkte

Hallo uaglp,

nein, eine derartige Konvention gibt es nicht. Allgemeine Grammatiken erlauben alle Produktion über die beliebige Iteration der Menge (N∪T)+ ×(N∪T)* (Vl. Kap. 1-9). Das "+" und das "*" sind hochgestellt, was bedeutet, dass auf der linken Seite jeder Produktion mindestens ein Nonterminal- oder Terminalsymbol stehen muss und auf der rechten Seite sogar noch das leere Wort.

Nun zu deiner Grammatik und der Aufgabe:

Im Aufgabentext ist eine rechtslineare Grammatik gefordert. Diese erlauben Produktionen der Form P ⊆ N × (T ∪ TN ∪ {λ}), also z.B. S-> a | aS | λ. Deine Produktion S-> 1100A ist selbstverständlich nicht aus dieser Menge.

Dennoch lässt sich deine Grammatik sehr schnell in eine rechtslineare Grammatik umschreiben (siehe Lösung).

Gruß

Philip (Tutor)

 

Beantwortet 22, Okt 2014 von utdbu utdbu Tutor(in) (106,580 Punkte)  
...