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 sprachen minimierung nichtdeterministisch huffman fehler-in-aufgabe chomsky-normalform anwesenheitsübung rechtslinear heimübung flip-flop cocke-younger-kasami-algorithmus kontextsensitive-grammatik kontextfreie-grammatik huffman-kodierung hauptklausur fehlererkennbarkeit vorlesungsfolien kontextfreie-sprache polynomialzeitreduktion faq gleitkommazahl fehlerkorrigierbarkeit rechtslineare-grammatik dateiorganisation cache darstellung-klausur nachklausur xwizard adressierungsarten lambda mealy konjunktive-normalform pipelining zustände saalübung leeres-wort endliche-automaten 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 klausureinsicht disjunktive-normalform pumping-lemma info-ii bussysteme rechnerarchitektur abzählbarkeit komplexitätsklassen ableitungsbaum vorlesungsaufzeichnung round-robin minimierung-endlicher-automaten chomsky-klassen binärzahl entscheidbar programmiersprachen entscheidbarkeit aufzählbarkeit stern-symbol automaten nukit-fragen bewertung zugriffsarten von-neumann-rechner umformung adressierung mengen binär-subtrahieren organsiation

Kategorien

2 Pluspunkte 0 Minuspunkte
119 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
...