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

1 Pluspunkt 0 Minuspunkte
162 Aufrufe

Guten Abend,

 

leider verstehe ich die folgenden Zeilen nicht bei Tut 2 A7 b)

 

(s0, λ, k0)(s4, k0)

Wieso gilt denn hier das ? Weil durch das Sternchen (a,b)* auch für i=j=k=0 wir in einen Endzustand kommen müssen ?

(s1, a, a) (s3)

Wenn mein j=0 ist, dann springe ich gleich in den Zustand s3. Ist deshalb der KA ndet ?

(s2,λ,k0)(s4,k0)

Kann mir jemand erklären, was wir hier machen ?

Normalerweise lese ich in Zustand s2 b´s und lösche meine a´s damit. Wenn ich nun keine b´s habe, wieso bin ich dann in einem Endzustand. In meinem Keller befinden sich doch dann immer noch a´s und in einem Endzustand kann ich mich nur befinden, wenn mein Keller leer ist..

 

Beste Grüße

 

 

 

 

 

 

 

in HU-2-3 von uqdrx uqdrx Eins-Komma-Null-Anwärter(in) (4.3k Punkte)  

1 Eine Antwort

1 Pluspunkt 0 Minuspunkte
Hallo uqdrx,

genau, die Regel $ (s_0, \lambda , k_0) \rightarrow (s_4, k_0 ) $ ist hinzugefügt, dass der Automat auch das leere Wort akzeptiert. Der Kellerautomat wird dadurch aber auch nichtdeterministisch – er kann, falls als nächstes Zeichen ein $ a $ folgt und er sich in Zustand $ s_0 $ befindet "entscheiden", ob er direkt das $ a $ einliest (und die zweite Regel befolgt) oder ein $ \lambda $ "einfügt (und die erste Regel befolgt). Etwas formaler ausgedrückt ergibt sich durch diese "Wahl" ein Konfigurationsbaum, in dem wir alle Möglichkeiten betrachten.

Die Zeile $ (s_1 , a , a) \rightarrow (s_3 , \lambda ) $ sorgt dafür, dass auch Wörter behandelt werden können, die kein $ b $ enhalten. Der Automat macht dies – ähnlich wie die Kellerautomaten, die Palyndrome erkennen – indem er an jeder möglichen Stelle im Wort eine Möglichkeit einräumt, dass gerade die Mitte des Wortes erreicht ist. Deswegen gibt es auch immer eine Konfigurationsfolge, die bei einem Wort mit einer gerade Anzahl an $ a $ in einem Endzustand mit einem leeren Keller endet.

Ich hoffe, ich konnte etwas helfen, wenn nicht, frag' gerne nochmal nach :)

Viele Grüße

Jonas (Tutor)
von ufdzo ufdzo Tutor(in) (103k Punkte)  
0 0
Hallo Jonas,

Aber nur wegen dem * gilt (s0,λ,k0)→(s4,k0) oder ? Bei einem + würde diese Zeile entfallen ?

Und was besagt diese Zeile (s2,λ,k0)→(s4,k0)?

Vielen Dank für deine Hilfe !:)
0 0
Genau, bei einem + wäre das leere Wort nicht mehr Element der Sprache und wir müssten auch im Automaten nicht mehr dafür sorgen, dass das Wort angenommen wird.
Die Zeile $ (s_0 , \lambda , k_0 ) \rightarrow (s_4 , k_0 ) $ sorgt dafür, dass auch Wörter akzeptiert werden können, die die Struktur $ w = a^nb^n, n \in IN $  akzeptiert werden können. Das ist durch den Kommentar in der Lösung angedeutet ($ k = 0 $ heißt gerade, dass es keine $ a $ am Ende des Wortes gibt).
...