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

0 Pluspunkte 0 Minuspunkte
23 Aufrufe

 Hallo,

ich habe eine Frage zur  Keller Automaten von Aufgabe 8): 

1. ist die Beschreibung von Überführungsfunktion flexibel? oder gibt eine fest Regel (wie in Vorlesung 3 s. 7 steht): ?

Beispiel 1:8a) δ4: (s0; b; a) - (s1; ba): ist hier richtig?  warum schreibt man hier nicht (s0; b; a) - (s1; λ)? da ein b gelesen wurde, dann wird ein a in der Keller gelöscht oder ?

Beispiel 2:8b) δ5: (s0; a; k0) - (s1; ak0): warum muss man hier Zustand wechseln? weil in 8a) ist der Zustand geblieben:(s0; a; k0) -(s0; ak0)

2. kann sein die Lösung  für das Testwort  am Ende ein λ fehlt. 

z.b L4: (s3; λ; k0) -(s4; k0): soll sollte (s4; λ; k0) statt (s4k0) schreiben oder?

genauso wie bei L5: (s3; λ; k0) (s4; k0)

3. wie kann man überprüfen, ob Überführungsfunktion komplett geschrieben ist? Gibt ein Verfahren, wie man die Überführungsfunktion schreibt?

Dank sehr im Voraus

in AU-2-3 von uqyws uqyws Lernwillige(r) (730 Punkte)  
Bearbeitet von uqyws uqyws

1 Eine Antwort

0 Pluspunkte 0 Minuspunkte
 
Beste Antwort

Hallo uqyws,

1. Die Beschreibung der Überführungsfunktion ist so geregelt, wie auf den Folien, also etwas in den Keller schreiben und löschen eventuell noch nichts machen. Man braucht also nur die Idee, wie man die Grammatik dann mit diesen Regeln anwenden kann.

Zum Bsp 1: Die Grammatik lautet a^mb^na^nb^m, es gibt also gleich viel a's am Anfang wie b's am Ende und in der Mitte gleich viele b's wie a's. n und m können unabhängig von einander gewählt werden. Im Zustand s0 werden nur die a's gesammelt und gemerkt, bis der Mittelteil (b^na^n) abgearbeitet wurde. Sobald das erste b kommt sind wir im Zustand s1 und merken uns alle b's (und n>=1, also kommt auf jeden Fall ein b). In s2 müssen genau so viele a's kommen wie b's gerade eben (n Stück) und wenn dann alle a's abgearbeitet sind haben wir immer noch m Stück im Keller für die kommenden b's.

Also man braucht die Zustände wirklich aufgrund der Form der Grammatik.

Zu Bsp 2: Man muss nicht zwingend den Zustand wechseln, es geht auch ohne. Zur Strukturierung kann es helfen, in s1 geht man, wenn das Wort nichtleer ist.

2. Du kannst (s4; λ; k0) schreiben, ist auf jeden Fall kein Fehler. Es ist Konvention, dass man das am Ende auch weglassen kann, wenn das Wort abgearbeitet ist und man im Endzustand ist, schaden tut es dennoch nicht.

3. Ein Verfahren gibt es so direkt nicht, man sollte die Grammatik noch einmal anschauen und auch Sonderfälle beachten. Dann kann man seinen Automaten Schritt für Schritt durchgehen, ob die alle berücksichtigt werden. Aber einen garantierten Weg gibt es leider nicht.

Ich hoffe, ich konnte dir weiterhelfen, viel Erfolg noch beim Lernen und viele Grüße

Anne (Tutorin)

von uvlwv uvlwv Info-Genie (9.4k Punkte)  
ausgewählt von uqyws uqyws
0 0
Alles Klar
Vielen Dank
...