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

Beliebteste Tags

verständnis alternativlösung klausur kellerautomat endlicher-automat grammatik regulärer-ausdruck turingmaschine pumpinglemma tipp zahlendarstellung cmos bonusklausur klausurrelevant komplexität schaltwerk binary-decision-diagram deterministisch assembler schaltnetz minimierung sprachen nichtdeterministisch huffman chomsky-normalform fehler-in-aufgabe anwesenheitsübung rechtslinear heimübung flip-flop huffman-kodierung cocke-younger-kasami-algorithmus kontextsensitive-grammatik kontextfreie-grammatik fehlererkennbarkeit hauptklausur vorlesungsfolien polynomialzeitreduktion kontextfreie-sprache faq gleitkommazahl fehlerkorrigierbarkeit rechtslineare-grammatik dateiorganisation cache darstellung-klausur nachklausur xwizard adressierungsarten mealy lambda endliche-automaten konjunktive-normalform pipelining zustände saalübung leeres-wort moore ohne-lösungen betriebssystem speicherorganisation monotone-grammatik 2-komplement hammingzahl lösungsweg fehler pumping-lemma-für-kontextfreie-sprachen pumping-lemma reguläre-sprache monoton kodierung berechenbarkeit klausureinsicht disjunktive-normalform abzählbarkeit info-ii bussysteme rechnerarchitektur entscheidbarkeit komplexitätsklassen chomsky-klassen ableitungsbaum vorlesungsaufzeichnung round-robin aufzählbarkeit minimierung-endlicher-automaten von-neumann-rechner binärzahl entscheidbar programmiersprachen stern-symbol automaten schaltnetze-und-schaltwerke nukit-fragen bewertung zugriffsarten umformung adressierung mengen binär-subtrahieren

Kategorien

1 Pluspunkt 1 Minuspunkt
204 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
in HU-2-3 von uhdwv uhdwv Lernwillige(r) (200 Punkte)  

2 Antworten

3 Pluspunkte 0 Minuspunkte

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)

 

 

von uodvo uodvo Tutor(in) (107k Punkte)  
0 0
Vielen Dank für die Antwort.
2 Pluspunkte 0 Minuspunkte

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

 

von Dozent (10.1m Punkte)  
Bearbeitet von
...