Aufgabe 1.6

Benutzeravatar
Ibliss
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 209
Registriert: 11. Apr 2008 04:08
Wohnort: Darmstadt

Aufgabe 1.6

Beitrag von Ibliss » 14. Mär 2015 21:43

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
?
"Honesty is the first chapter in the book of wisdom.
Alien vs Predator 2 is the movie version of that book."

DanielAW
Erstie
Erstie
Beiträge: 11
Registriert: 17. Nov 2014 22:47

Re: Aufgabe 1.6

Beitrag von DanielAW » 15. Mär 2015 18:35

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

Benutzeravatar
Ibliss
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 209
Registriert: 11. Apr 2008 04:08
Wohnort: Darmstadt

Re: Aufgabe 1.6

Beitrag von Ibliss » 15. Mär 2015 18:52

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.
"Honesty is the first chapter in the book of wisdom.
Alien vs Predator 2 is the movie version of that book."

Jens Huthmann
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 192
Registriert: 10. Nov 2011 19:42

Re: Aufgabe 1.6

Beitrag von Jens Huthmann » 16. Mär 2015 15:49

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.

Antworten

Zurück zu „Archiv“