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.)

Schöne Ferien!
 

 

Kellerautomat Zustandsüberführungsfunktion

+2 Punkte
224 Aufrufe
laut Definition aus dem Buch heißt es für die KA Zustandsüberführungsfunktion:

entweder $\delta(s, e, k) = (s', v)$ oder $\delta(s, \lambda, k) = (s', v)$ mit $e \in E$, $s,s' \in S$, $k \in K$, $v \in K^\star$.

$v$ stellt hier eine Zeichenkette dar, die beliebig lang sein kann ( also auch $\lambda$). Hab ich das richtig verstanden? Mir ist nicht ganz klar wann es sich anbietet $|v| > 1$ zu verwenden? Kann mir jemand eine Beispielsprache nennen? Vor allem da ich eigentlich verinnerlicht hatte, dass nur EIN Zeichen aus dem Keller gelöscht und EIN Zeichen reingeschrieben werden kann. Bezieht sich $v$ hier etwa auf den gesamten Kellerinhalt?
Gefragt 15, Nov 2016 in KEL-AA von uudua uudua Lernwillige(r) (430 Punkte)  
Bearbeitet 15, Nov 2016 von Lukas König
Es heißt LAMBDA!

Eine Antwort

+3 Punkte
 
Beste Antwort

Die Zeichenkette $v$ bezeichnet die Zeichen, die oben auf den Keller abgelegt werden. Das ist oft das leere Wort $\lambda$ oder eine Kette aus zwei Zeichen. Im ersten Fall wird das oberste Zeichen aus dem Keller entfernt und danach $\lambda$ hineingeschrieben, effektiv wird also das oberste Zeichen gelöscht.

Der zweite Fall ist, dass das oberste Zeichen gelöscht wird und stattdessen zwei Zeichen hineingeschrieben werden, der Keller wächst also um ein Zeichen an. Oft ist dabei das untere der beiden hineingeschriebenen Zeichen dasselbe, das zuvor schon im Keller stand, sodass effektiv nach dem Rechenschritt ein Zeichen auf den Keller oben abgelegt wurde.

Eher selten (im Kontext der Vorlesung), aber genauso möglich sind Fälle, wo ein Zeichen in den Keller geschrieben wird, das bedeutet, dass das oberste Zeichen also einfach nur ersetzt wird, sowie Fälle, wo mehr als zwei Zeichen in den Keller geschrieben werden. Um die Sprachmächtigkeit des Kellerautomaten zu erhalten, ist es wichtig, dass beliebig lange Zeichenketten für $v$ zugelassen werden. Einen Anwendungsfall dafür sehen Sie etwa im Buch auf Seite 179 (oder auf den Folien ab 3-24), wo ein Algorithmus zur Konstruktion eines Kellerautomaten zu einer beliebigen Kontextfreien Grammatik präsentiert wird.

Beantwortet 15, Nov 2016 von Lukas König Dozent (10,065,100 Punkte)  
ausgewählt 15, Nov 2016 von uudua uudua
Vielen Dank!
...