Konvention bei Produktionen

Question

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

Answer 1

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)