Aufgabe HU - 2 -3 b)

Question

Hallo,

es geht um HU - 2- 3 Teilaufgabe b)

ich bin mir nicht sicher ob meine Lösung richtig ist, und da sie sich doch von der ML unterscheidet, wollte ich hier einmal nachfragen.

 

Zuerst die Grammatik ( Ich schreibe nur die Regelmenge auf aus Platzgründen)

 

S --> aSa / lambda

S --> aXb

X--> aXb

X --> lambda

 

hier bin ich mir zum einen nicht sicher ob man so mit lambda verfahren darf, zum anderen ob zwei Produktionen mit identischer rechter Seite erlaubt sind?

 

Nun zum Kellerautomaten. Meiner ist etwas kürzer als die ML, weshalb ich schon etwas stutzig war, aber ich finde keinen Fehler.

Auch hier nur die Übergänge: Endzustand=Startzustand =S0 !

(S0,a,k0) --> (S1,ak0)

(S1,a,a) --> (S1,aa)

(S1,a,a) --> (S2,lambda)

(S1,b,a) --> (S2,lambda)

(S2,b,a) --> (S2,lambda)

(S2,a,a) --> (S2,lambda)

(S2,lambda,k0) --> (S0,k0)

 

Ist die Aufgabe so korrekt gelöst?

Vielen Dank

Answer 1

Hallo,

du darfst λ hier so verwenden, da nach keiner bestimmten Grammatik gefragt war.
Zwei Produktionen mit identischer rechter Seite sind erlaubt.

Der Kellerautomat ist so leider nicht richtig. Schau dir zum Beispiel das Wort aaab an, das nicht in der Sprache liegt, die dieser Kellerautomat akzeptieren sollte. 
Eine mögliche Konfigurationsfolge wäre:

(s0,aaab,k0) --> (s1,aab,ak0) --> (s1,ab,aak0) --> (s2,b,ak0) --> (s2,λ,k0) --> (s0,k0)

Da der Kellerautomat im Endzustand s0 landet und das Wort vollständig abgearbeitet wurde, akzeptiert er das Wort, obwohl er das eigentlich nicht sollte.

 

Viele Grüße,

Julia (Tutorin)

 

 

Comments

Vielen Dank für die Antwort.

Answer 2

Sie können, wenn Sie die Produktionen / Zustandsübergänge nur ein bisschen anders formatieren, die Grammatik und den Kellerautomaten in den XWizard eingeben und sich die Simulation anschauen. (Tipp für den XWizard: Wählen Sie einfach ein Beispiel aus und passen Sie die Teile an, die Sie anders haben wollen.)

Ihr Kellerautomat: http://www.xwizard.de:8080/Wizz?template=ID-19100

Zugehöriges Skript:

pda: (S0,a,k) => (S1,ak); (S1,a,a) => (S1,aa); (S1,a,a) => (S2,lambda); (S1,b,a) => (S2,lambda); (S2,b,a) => (S2,lambda); (S2,a,a) => (S2,lambda); (S2,lambda,k) => (S0,k); --declarations-- s0=S0; /* Startzustand */ F=S0; /* Endzustände */ kSymb=k; /* Bezeichner für $k_0$ */ inputs=aaab; /* Eingegebenes Wort */ --declarations-end--

 

Dabei sehen Sie auch das Problem, das Julia angesprochen hat: das Wort $aaab$ sollte nicht akzeptierbar sein. Die Grammatik scheint zu stimmen:

Ihre Grammatik: http://www.xwizard.de:8080/Wizz?template=ID-19107

Zugehöriges Skript:

grammar: S => a, S, a | epsilon | a, X, b; X => a, X, b | epsilon; --declarations-- N=S,X; /* Nichtterminale */ T=a,b; /* Terminale */ S=S; /* Startzeichen */ maxdepth=100; /* Maximale Baumtiefe */ maxLengthWords=10; /* Maximale Wortlänge im Baum */ --declarations-end--