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

0 Pluspunkte 1 Minuspunkt
40 Aufrufe
Könnte mir jmd die Übergänge erklären? Die sind mir irgendwie nicht so eindeutig...
in KEL-AF von utdbu utdbu Tutor(in) (107k Punkte)  

1 Eine Antwort

0 Pluspunkte 0 Minuspunkte

Hallo,

hier ist eine grobe Beschreibung der Idee:

Zuerst einmal wissen wir, dass die Wörter aus der Sprache eine gerade Anzahl an b's haben und immer auf aab enden müssen.

s0 = Startzustand, und Zustand, in dem die Anzahl der b's gerade ist 

s1 = Zustand, in dem die Anzahl der b's ungerade ist

s2 = Zustand, der nach dem ersten a schaut, ob das zweite a folgt

s3 = Zustand, der nach dem zweiten a schaut, ob ein b folgt

se = Endzustand

Wenn wir in s0 starten und ein b einlesen, dann haben wir eine ungerade Anzahl an b's, also rüber in s1. Beim nächsten b in s1 sind wir wieder im geraden Bereich, also wechseln wir zurück in s0. Und so kann man dann hin und her wechseln solange wir weiter b's einlesen.

Wenn wir in s0 sind und ein a einlesen, dann wissen wir, dass wir uns damit schon im Endteil "aab" des Wortes befinden müssen. Also wird der Zustand gewechselt in s2, und dort an wird dann weiter geprüft, ob der weitere Verlauf des Wortes wirklich "aab" entspricht.

Hoffe, das konnte dir einen Überblick verschaffen :)

Viele Grüße,

Vivian (Tutor)

 

von utdbu utdbu Tutor(in) (107k Punkte)  
0 0
Dass einzige was mich noch leicht verwirrt, ist, das am Ende immer ko steht.
0 0
Hallo,

lass dich nicht davon verwirren. Hier steht am Ende immer ko, weil unserer Kellerautomat den Keller gar nicht benutzt bzw. braucht. Allerdings gibt es mehrere richtige Lösungen und es ist egal ob du den Keller benutzt oder nicht.

Einfachere Sprachen können ohne den Keller erkannt werden, aber für komplexere Sprache ist sowas nicht mehr möglich. Z.B für die Sprache a^nb^n brauchst du den Keller  um die Sprache erkennen zu können, weil du irgendwie zählen muss, wie viele a bzw b vorgekommen sind.

Grüße

Antonio

(Tutor)
...