Kontextfreie Grammatiken

[Ritus]

Hi, gibt es Tricks, um für eine gegebene Sprache möglichst einfach eine kontextfreie Grammatik zu konstruieren? Hänge bei diesen beiden Aufgaben:

Geben Sie für die Sprachen:

S = { a^i b^3i | i >= 1} und
S2 = { a^n (bc)^n-1 | n > 0}

jeweils eine kontextfreie Grammatik an.

Mir ist schon vollkommen klar, wie die Wörter der Sprache aussehen, allerdings komme ich nicht auf die Produktionsregeln der Grammatik..

 

[Horst Schlemmer]

Das ist bei mir schon ein wenig her, aber soweit ich weiß gibts da kein wirkliches Standardverfahren. Allerdings sieht man das mit ein wenig Übung irgendwann einfach.

Bei deinen Beispielen:

a)
S -> aAbbb
A -> aAbbb | Epsilon
b)
S -> aA
A -> aAbc | Epsilon

zu a)

Du brauchst für jedes a 3 mal so viele b, mindestens 1 mal. Das kleinste Wort wäre also abbb, das kann man ganz gut als Ausgangssituation nutzen. Um die Worte dann in beliebiger Länge zu erkennen nimmt man ne Produktionsregel und schiebt sie zwischen die a und b und lässt sie das Wort immer um ein a und drei b verlängern, bevor man irgendwann mit epsilon abbricht.

b)
Du brauchst ein a mehr als bc, also beginnst du mit einem a und erzeugst dann über A immer genauso viele a wie bc, wie im ersten Beispiel.

 

[Ritus]

Wtf, so einfach. Vielen Dank!