Aufgabe reguläre Grammatik
-
Ich muß folgende Aufgabe lösen.
Konstruieren Sie eine reguläre Grammatik G2, die Zeichenfolgen über dem
Alphabet T = {w, x, y, z} definiert. Alle Worte aus L(G2) bestehen aus mindestens
einem Zeichen, wobei w beliebig oft vorkommt. Das x steht nur einfach, y nur in
Doppeln und z nur in Tripeln (diese jeweils nicht mehrfach hintereinander).
Beispiele:w ∈ L(G2), wxwyyzzz ∈ L(G2), xw ∈ L(G2), yyzzzyy ∈ L(G2), zzzyyxwxyy ∈ L(G2)
wy ∉ L(G2), xyyzz ∉ L(G2), z ∉ L(G2), xyyyyxzzzw ∉ L(G2), wzzzzzzx ∉ L(G2)ε-Produktionen, also Produktionen mit leerer rechter Seite, dürfen nicht verwendet
werden.Nun meine Frage. Da es sich ja um eine reguläre Grammatik handelt. Wäre ja hier nur ein Terminal oder ein Terminal gefolgt von einem Nichtterminal zulässig.
Also so in der etwa:N = {A} T={w,x,y,z} P={ A -> w (1) A -> x (2) A -> y (3) A -> z (4) A -> wA (5) A -> xA (6) A -> yA (7) A -> zA (8) }Aber dadurch kann ich ja nicht die ungültigen Beispiele verhindern. Oder ist es doch erlaubt mehrere Terminal auf der linken Seite zu haben?
Grüße
eddi
-
Du könntest mal verschiedene Non-Terminale verwenden. Aber in jeder Regel nur eins links und eins rechts.
-
Habe momentan das raus:
N = {S,A,B,C,D,E,F,G,H,I,J,K} T={w,x,y,z} P={ S -> A | B | C | D | E | H (1) A -> wA | wB | wC | wD | wE | wH (2) B -> w (3) C -> xA | xB | xE | xH (4) D -> x (5) E -> yF | yG (6) F -> yA | yB | yC | yD | yH (7) G -> Y (8) H -> zI (9) I -> zJ | zK (10) J -> zA | zB | zC | zD | zE | zF | zG (11) K -> z (12) }Bin ich so auf der richtigen Spur? Vielleicht ist das ja sogar richtig
Die Beispiele lassen so so bilden, und die flaschen nicht.Kann man das denn so schreiben? Oder muß ich jede Regel einzel nacheinander schreiben?
Grüße
eddi
-
Kann man so schreiben. Ob die einzelnen Regeln jetzt richtig sind, hab ich jetzt nicht überprüft... aber aufn ersten Blick könnte es hinkommen.
-
Vielen Dank.