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

0 Pluspunkte 0 Minuspunkte
30 Aufrufe
Hallo, da die Lsg sehr kurz gefasst ist und ich auf eine andere Lsg gekommen bin wollte ich sicher gehen, dass meine Lsg auch "richtig" ist:

Delta:

(S0, lambda , ko) → (Se, k0)

(S0, a , ko) → (S1, ak0)

(S1, a , ko) → (S1, ak0)

(S1, a , a) → (S1, lambda)

(S1, b, ko) → (Se, k0)

(S1, b , ko) → (S1, bk0)

(S1, a , b) → (S1, ab)

(S1, b , b) → (S1, lambda)

(S1, lambda , ko) → (Se, k0)

Vielen Dank und Liebe Grüße!
in Band I, Kapitel 5 von uuiya uuiya Lernwillige(r) (680 Punkte)  

1 Eine Antwort

0 Pluspunkte 0 Minuspunkte

Hey uuiya,

deine Lösung sieht leider nicht richtig aus. 

Erste Sache, die es unbedingt zu vermeiden gilt: Die folgenden zwei Übergange sind uneindeutig - du definierst also zwei Möglichkeiten, was passieren kann, wenn man sich in S1 befindet, b einliest und k0 im Keller steht. Damit könnte ein Automat nicht arbeiten.

(S1, b, ko) → (Se, k0)
(S1, b , ko) → (S1, bk0)

Ansonsten kann ich deiner Idee an mehreren Stellen nicht ganz folgen - kannst du vielleicht erklären, was dein Ansatz war? Schauen wir uns beispielsweise deine Übergänge 2-4 an. Dort modellierst du den Automaten so, dass er beliebig viele a's nacheinander akzeptiert. Per Definition in der Aufgabenstellung soll er aber eben nur die Kombination a2b enthalten, und zwar n-mal. Du willst also immer genau 2 a's, dann ein b. Dann ggf. nochmal von vorn. 

Vielleicht hilft das schon, um deinen Fehler zu erkennen, aber stell gerne nochmal eine Rückfrage, wenn etwas unklar ist.

Beste Grüße,

Martin (Tutor)

von usifu usifu Eins-Komma-Null-Anwärter(in) (3.0k Punkte)  
0 0
Hey Martin,
erstmal vielen Dank für die Antwort und für die Tipps!

Also ehrlich gesagt kann ich dir auch nicht mehr den Ansatz verraten:D ich sehe jetzt bloß auch, dass der KA von mir auf jeden Fall falsch ist.

Ich hab mich grade nochmal hingesetzt und nochmal romprobiert:
Mein Ansatz ist folgender:

1) Ich hab das leer Wort enthalten -> ich kann ohne Eingabe in den Endzustand

2) Als erstes kann ich nur ein a lesen, ich schreibe es in den Keller Wechsel den Zustand in s1.

3) Lese in s1 ein a ein und hab im Keller oben ein a stehen. "Lösche das eine a  mit dem anderen a"(=lambda). Wechsel den Zustand in s2.

4) Dort kann ich ja nur noch ein b einlesen. Dieses lese ich ein schreibe aber nichts in den Keller. (das darf ich ja oder?)
Wechsel den Zustand in s0. (Darf ich das auch, oder??)

So kann es jetzt sein, dass ich keine Eingabe mehr habe -> Endzustand, oder eben wieder "von vorne" anfange.

Konkret:

(S0, lambda , ko) → (Se, k0)

(S0, a , ko) → (S1, ak0)

(S1, a , a) → (S2, lambda)

(S2, b , ko) → (S0, ko)

Wie siehts damit aus?:D

Vielen Dank und Liebe Grüße!
0 0
Hey,
das sieht für mich soweit schlüssig aus, müsste auch funktionieren.
Beachte aber unbedingt, dass in dieser Aufgabe ein Spezialfall vorliegt! Hier ist ausnahmsweise nicht explizit ein deterministischer(!) KA gefragt, nur deswegen ist deine Lösung so zulässig. Die Musterlösung im Übrigen ebenso.
Also in der Klausur unbedingt darauf achten, was gefragt ist - sowas kann einfache Punkte kosten :)
Liebe Grüße!
0 0
Top! Dankeschön :)
...