Aufgabe 1.6

[Ibliss]

Guten Tag, die Musterlösung der Aufgabe lautet
G = ({S, X, Y,R}, {a, b, c, d, e, f}, P, S), P :
S ::= aR | d
R ::= bXS | cY S
X ::= e | f
Y ::= a | b

Wäre das auch eine gültige Lösung:
G = ({S, X, Y}, {a, b, c, d, e, f}, P, S), P :
S ::= a(bXS | cYS) | d
X ::= e | f
Y ::= a | b
?

[DanielAW]

Hi,

das würde mich auch interessieren, aber müsstest du bei dir nicht nochmal die "Linksrekursion" entfernen?
Ich wäre dann auf folgendes gekommen:

Code: Alles auswählen

S ::= a(bX(S)*| cY(S)*)|d
X ::= e|f
Y ::= a|b

[Ibliss]

Hi,

das würde mich auch interessieren, aber müsstest du bei dir nicht nochmal die "Linksrekursion" entfernen.
Ich wäre dann auf folgendes gekommen:

Code: Alles auswählen

S ::= a(bX(S)*| cY(S)*)|d
X ::= e|f
Y ::= a|b

Ich glaube hier ist keine Linksrekursion im Spiel

Code: Alles auswählen

S ::= a(bXS | cYS) | d

eine Linksrekursion ist von solcher Form

Code: Alles auswählen

S ::= SY

also S taucht auf linker Seite wieder auf.

Etwas ist faul an Deiner Umformung. Aus

Code: Alles auswählen

S ::= a(bX(S)*| cY(S)*)|d
X ::= e|f
Y ::= a|b

kann man zum Beispiel abe herleiten, aber ausgehen von der ursprünglichen Produktion

Code: Alles auswählen

S ::= abXS | acYS | d
X ::= e | f
Y ::= a | b

nicht.

[Jens Huthmann]

Wäre das auch eine gültige Lösung:
G = ({S, X, Y}, {a, b, c, d, e, f}, P, S), P :
S ::= a(bXS | cYS) | d
X ::= e | f
Y ::= a | b
?

Das sieht richtig aus. Sie haben hier ja bloß die R Produktion mit den Klammern integriert.

Code: Alles auswählen

S ::= a(bX(S)*| cY(S)*)|d
X ::= e|f
Y ::= a|b

Der * nach dem (S) ist falsch da in der ursprünglichen Regel S nicht optional ist. Bei Ihnen kann das Wort ohne ein abschließendes d terminieren. In der ursprünglichen Grammatik ist immer ein d am Ende.