Kellerautomat Theoretische Informatik?
Hallo,
Ich habe den Kellerauromaten aus der Theoretischen Informatik soweit verstanden, allerdings weiß ich nicht wie man die delta-Funktion nun aufschreibt. Man bildet dabei ja eine Kombi aus Zustand, Kellersymbol und Buchstabe auf ein Wort über dem Kelleralphabet und einem Zustand ab. Was sind hier aber diese Worte über dem Kelleralphabet?
Danke
2 Antworten
Das Kelleralphabet besteht aus Symbolen, die im Keller abgelegt werden können. Ein Wort über diesem Alphabet entspricht einer endlichen Kombination dieser Symbole.
Ein Beispiel. Sagen wir, du möchtest folgende Sprache erkennen:
a^n(bc)^2n
Dabei sei:
E = {a, b, c}; dein Eingabealphabet
K = {b, c}; dein Kelleralphabet
Und du hast folgende Deltafunktion:
delta(z0, a, {b, c, epsilon}) => (z0, bc); //Zu beachten: das b liegt oben im Keller. Je nach Konvention muss es evtl. cb statt bc lauten.
delta(z0, b, b) => (z0, epsilon);
delta(z0, b, c) => (z_error, epsilon);
delta(z0, b, epsilon) => (z_error, epsilon);
delta(z0, c, b) => (z0_error, epsilon);
delta(z0, c, c) => (z_end, epsilon);
delta(z0, c, epsilon) => (z_error, epsilon);
man ist im Zustand z0 liest ein b und schreibt ein b auf den Stack.
Man liest einen Zustand zo, eine Eingabe b und ein Kellersymbol b ein. Dann kommt man in den Zustand z0 und legt ein oder mehrere Kellersymbole in den Keller/auf den Stack.
Das Epsilon heißt, das kein Kellersymbol in den Keller gelegt wird. Epsilon ist das leere Wort.
Soweit verstanden?
Was ich gerade nicht verstehe ist das Kellersymbol: Man liest ein b in den Keller aber man legt nichts auf den Stack. Das ist gerade der Punkt der mich verwirrt
Ok das hilft mir weiter. In meinem Kurs haben wir aber solche Arten von Übergängen noch nicht angeschaut. Bei uns läuft es so ab: Man liest ein Zeichen aus dem Eingabealphabet und setzt oder nimmt ein Kellerzeichen auf/vom Stack. Wir lesen also nicht davor noch zusätzlich ein Zeichen aus dem Kelleralphabet. Oder ist das das Gleiche?
Was ist ein Kellerautomat?
https://de.wikipedia.org/wiki/Kellerautomat
Ein theoretisches Konstrukt der Informatik.
Danke, aber wie muss ich hier die delta-Funktion verstehen. Bsp. 2: man ist im Zustand z0 liest ein b und schreibt ein b auf den Stack. Dann kommt man dadurch in den Zustand z0 und was soll jetzt das epsilon?