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

1 Pluspunkt 0 Minuspunkte
134 Aufrufe
Ich hätte eine Frage bezüglich der Fragen zur Selbstkontrolle im Buch , und zwar die zweite Frage : Bei einem endlichen Automaten, der das leere Wort akzeptiert, muss der Startzustand s0 ein Endzustand sein. Bei einem Kellerautomaten aber nicht- warum ?".

Endlich Automaten, können das aktuelle Zustand merken, aus einem Zustand s0 muss für eine Eingabe "lambda" ein Endzustand erreicht werden, das Kellerautomat besitzt hingegen ein kellerspeicher der die Eingabe speichern kann, er kann also eine Reihe von zustände annehmen, und dann in einem endzustand (anders als s0) bei eingabe von lambda, halten und das wort akzeptieren. Oder sind bei Kellerautomaten lambda übergänge erlaubt, was bei endlichen Automaten nicht der Fall ist ?

Es ist mir nicht klar wie ich die Frage beantworten kann.

Es wäre sehr nett , wenn jemand mir helfen könnte.
in Kapitel 2 von  

1 Eine Antwort

1 Pluspunkt 0 Minuspunkte
 
Beste Antwort

Hey,

Erstmal zum endlichen Automaten: Hier die Zustandsüberführungsfunktion definert, in welche Folgezustand\Folgezustände ein endlicher Automat nach dem Lesen eines Zeichens wechselt. D.h. - liest das Automat nichts, dann wird es auch nicht wechseln. Deswegen, muss per Definition der Startzustand auch ein Endzustand sein - bei Eingabe das leere Wort wird nichts gelesen, und deswegen wechselt das Automat nicht.

Jetzt zur Kellerautomaten: Wir solten erstmal ganz genau anschauen was ein "lambda" übergang bedeutet. 

Falls δ(s, λ, k) definiert ist, ignoriert KA das Eingabeband und verändert nur Keller und Zustand. 

D.h. ein lambda übergang heißt nicht "wir bekommen die Eingabe lambda - und danach pasiert was" - es heißt "falls mein Keller sich in der passende Zustand befindet, kann ich das Eingabeband ignorieren und ohne das Lesekopf zu bewegen, ein Zustandswechsel durchführen".

Deswegen beim Kellerautomaten kann man ein übergang  δ(s0, λ, k0) → (se,  k0) definieren, was die Möglichkeit bietet direkt in der Endzustand (ohne Eingabe) zu wechseln.

Ich hoffe das hilft.

Viele Grüße,

Kaleb

von urdxp urdxp Tutor(in) (102k Punkte)  
ausgewählt von Marlon Braun
...