Theoretische und technische Informatik - ganz praktisch
Herzlich willkommen auf der Question/Answer-Plattform zu Grundlagen der Informatik II. Wir wünschen Ihnen viel Spaß beim Lernen und Diskutieren!
Loggen Sie sich mit Ihrem KIT-Account (u...) ein, um loszulegen!
Beachten Sie auch diese Informationen zum Schnelleinstieg.
(Nicht-KIT-Studierende beachten bitte diese Informationen.)

Aufgabe HU - 2 -3 b)

0 Punkte
157 Aufrufe
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
Gefragt 1, Dez 2016 in HU-2-3 von uhdwv uhdwv Lernwillige(r) (200 Punkte)  

2 Antworten

+3 Punkte

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)

 

 

Beantwortet 1, Dez 2016 von uodvo uodvo Tutor(in) (106,530 Punkte)  
Vielen Dank für die Antwort.
+2 Punkte

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--

 

Beantwortet 1, Dez 2016 von Lukas König Dozent (10,065,100 Punkte)  
Bearbeitet 1, Dez 2016 von Lukas König
...