Frage zur Reihenfolge von Nonterminalzeichen

Question

Ich habe P versucht so zu lösen:

P={ S-> aAbB,

      A-> aAb I ab ,

     B-> cB I c}

Kann ich S so ableiten? Wenn nein wieso?

Answer 1

Hallo uagll,

mit deinen Produktionsregeln lässt sich das leere Wort nicht ableiten, was für n=0, m=0 aber Teil der Sprache ist. Der Schritt bei S -> AB das A durch aAb zu ersetzen ist in diesem Fall also nicht möglich.

Viele Grüße

Gregor (Tutor)

Comments

wäre das so dann richtig:

P= { S-> AB | (lammda),
        A -> aAb | ab | (lammda),
       B -> cB | c | (lammda)}

---

Ja, deine Lösung ist ähnlich wie die Musterlösung, einige der Produktionen kann man noch ersetzen, beispielsweise wird A -> ab durch aAb -> ab mit A -> lambda erzeugt. A -> ab muss somit nicht explizit aufgeschrieben werden. Da aber nicht nach einer minimalen Lösung gefragt wird, ist das in Ordnung.