Seite 1 von 1

Aufgabe 1.6

Verfasst: 14. Mär 2015 21:43
von 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
?

Re: Aufgabe 1.6

Verfasst: 15. Mär 2015 18:35
von 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

Re: Aufgabe 1.6

Verfasst: 15. Mär 2015 18:52
von Ibliss
DanielAW hat geschrieben: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.

Re: Aufgabe 1.6

Verfasst: 16. Mär 2015 15:49
von Jens Huthmann
Ibliss hat geschrieben: 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.


DanielAW hat geschrieben:

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.