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

2 Pluspunkte 0 Minuspunkte
167 Aufrufe
Ist auch direkt der Übergang (s0, &, k0) -> (SE, k0) möglich?

Meine Übergänge. Leider ist es mir aus unerfindlichen Gründen nicht möglich einen Ableitungsbaum im xwizard zu erstellen und ich weiß lediglich, dass das Testwort akzeptiert wird.
(s0, 1, k) => (s0, ak);
(s0, 0, k) => (s0, ak);
(s0, U, k) => (se, k);
(s0, 0, a) => (s0, aa);
(s0, 1, a) => (s0, aa);
(s0, U, a) => (s1, a);
(s1, 0, a) => (s1, a);
(s1, 1, a) => (s1, lambda);
(s1, lambda , k) => (se, k);
(se, 0 , k) => (se, k);

Vielen Dank und viele Grüße!
bezieht sich auf eine Antwort auf: alternativlösung
in 2015-B-02 von ukehj ukehj Lernwillige(r) (310 Punkte)  
0 0
Geben Sie mal Ihr komplettes XWizard-Skript an, dann können wir schauen, woran es liegt.
0 0
Das ist mein Skript. Ich habe normalerweise lediglich die Übergänge des vorher geposteten Skripts geändert.

pda:
(s0, 1, k) => (s0, ak);
(s0, 0, k) => (s0, ak);
(s0, U, k) => (se, k);
(s0, 0, a) => (s0, aa);
(s0, 1, a) => (s0, aa);
(s0, U, a) => (s1, a);
(s1, 0, a) => (s1, a);
(s1, 1, a) => (s1, lambda);
(s1, lambda , k) => (se, k);
(se, 0 , k) => (se, k);
--declarations--
s0=s0;
F=se;
kSymb=k;
inputs=01U110
--declarations-end--
0 0
Bei mir funktioniert das Skript: Sie bekommen eine Berechnungssequenz ausgegeben, und am Ende steht, dass das Wort akzeptiert wird. Was meinen Sie mit "Ableitungsbaum"? (Ableitungsbäume gibt es nur bei Grammatiken.)
0 0
Wenn ich auf Ihren xwizard-Link von der Aufgabe, auf die ich Bezug nehme, klicke, wird mir eine Art Ableitungsbaum angezeigt, die den Nichtdeterminismus durch aufspalten in die zwei möglichen Folgezustände (mit lambda in se oder mit 0 in s2) deutlich macht. Dies würde ich gerne auch haben, da mir der Nichtdeterminismus meiner Lösung noch nicht ganz klar geworden ist.
1 0
Ach so, das ist ein nichtdeterministischer Berechnungsbaum (das Wort "Ableitung" in der Lösung ist etwas irreführend). Dass es bei Ihnen keinen solchen Baum gibt, liegt daran, dass Ihre Lösung deterministisch ist. (Ich habe bei Marvin nachgefragt, warum er in seiner Antwort geschrieben hat, Ihre Lösung sei nichtdeterministisch - aus meiner Sicht ist das nicht korrekt.)

1 Eine Antwort

2 Pluspunkte 0 Minuspunkte

Hallo ukehj,

1. Dein Kellerautomat ist deterministisch, weshalb er eine Loesung zur Aufgabe ist.

2. Dein Kellerautomat passt abgesehen von 1. soweit.

3.  Der direkte Uebergang ist also in dem Fall moeglich.

Viel Erfolg,

Marvin (Tutor)

Update: Der Automat ist natuerlich deterministisch, da der Uebergang mit $ \lambda $ nicht von $ s_0 $ ist, bitte das zu entschuldigen!

von ucdxg ucdxg Tutor(in) (104k Punkte)  
Bearbeitet von ucdxg ucdxg
...