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 pumpinglemma turingmaschine tipp zahlendarstellung cmos klausurrelevant bonusklausur 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 cocke-younger-kasami-algorithmus kontextsensitive-grammatik kontextfreie-grammatik fehlererkennbarkeit huffman-kodierung hauptklausur vorlesungsfolien kontextfreie-sprache polynomialzeitreduktion faq gleitkommazahl fehlerkorrigierbarkeit rechtslineare-grammatik dateiorganisation cache darstellung-klausur nachklausur xwizard adressierungsarten lambda mealy endliche-automaten konjunktive-normalform pipelining zustände saalübung leeres-wort ohne-lösungen betriebssystem speicherorganisation moore monotone-grammatik 2-komplement fehler reguläre-sprache hammingzahl monoton lösungsweg pumping-lemma-für-kontextfreie-sprachen kodierung berechenbarkeit pumping-lemma klausureinsicht disjunktive-normalform info-ii bussysteme rechnerarchitektur abzählbarkeit komplexitätsklassen ableitungsbaum vorlesungsaufzeichnung round-robin entscheidbarkeit minimierung-endlicher-automaten chomsky-klassen von-neumann-rechner binärzahl entscheidbar programmiersprachen aufzählbarkeit stern-symbol automaten schaltnetze-und-schaltwerke nukit-fragen bewertung zugriffsarten umformung adressierung mengen binär-subtrahieren

Kategorien

1 Pluspunkt 1 Minuspunkt
197 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
...