nicht monotone Grammatik Vorschlag

Question

Hallo,

wäre dann diese nicht monotone Grammatik G' richtig ? :

G=(N,T,P,S) mit

P= {S --> XBY,

X -->XD|lambda,

DB --> BBD,

DY --> Y|Lambda,

B --> b}

Answer 1

Hallo,

nein die stimmt leider nicht.

Durch deine dritte Regel reichern sich am Ende des Wortes beliebig viele D's an.

Du hast aber nur ein Y, sodass du die Regel DY-->lambda nur einmal anwenden kannst und die D's nicht wegbekommst.

XBY-->XDBY--> XDDBY--> XDBBDY--> XBBDBDY--> XBBBBDDY--> XBBBBD--> BBBBD--> bbbbD

Das einzige Wort aus L, das sich produzieren lässt ist bb, soweit ich sehe.

Viele Grüße

Lukas (Tutor)

Comments

Vielleicht fehlt die Regel Y --> Lambda
da mit dieser und DY --> Y lassen sich alle b hoch 2 hoch n Wörter ableiten, denke ich.

XBY-->XDBY--> XDDBY--> XDBBDY--> XBBDBDY--> XBBBBDDY -->(Anwendung von DY-->Y) XBBBBDY --> XBBBBY (2. Anwendung von DY-->Y)--->BBBB (mit Anwendung von X-->Lambda und Y-->Lambda)

Sonst eine alternative Lösung wäre sehr hilfreich. Danke im voraus

Mit freundlichen Grüssen

---

Hab gerade nochmal drüber geschaut und gesehen dass du die D's am Ende ja doch auflösen kannst, durch die vorletzte Regel.

Das Wort w=b kannst du allerings trotzdem nicht erzeugen:
S-->XBY-->BY-->bY

Soweit ich sehe, müsstest du noch die Regel Y--> lambda einführen.

Ansonsten ist sie aber korrekt!

---

Da warst du schon schneller als ich. Ja genau, die Regel muss noch rein.

---

Perfekt !
Danke sehr