Keller-Automat: Palindrome

Vorlesung	Übungsaufgabe	vom
Thümmel: Formale Syntax	Keller-Automaten: Palindrome	15. Jan. 1998

nächste Aufgabe, Übersicht und vorherige Aufgabe

Keller-Automat für Palindrome

L = { xx^R | x = (ab)* }
Anmerkung: Die Sprache L enthält nur bestimmte Palindrome. Mit L₂ = { x Î {a, b}* | x = x^R } würde man alle Palindrome erfassen.

Ein Kellerautomat, der die Sprache L akzeptiert, sieht wie folgt aus:

K {q₀, q₁} endliche, nicht leere Menge von Zuständen

V {a, b} endliche, nicht leere Menge von Eingabesymbolen

s q₀ Anfangszustand s ÎK

F {q₀, q₁} Menge von Endzuständen

D (q₀, a, e) -> (q₀, X)
(q₀, a, Y) -> (q₀, YX)
(q₀, b, Y) -> (q₁, e)
(q₀, b, e) -> (q₀, Y)
(q₀, b, X) -> (q₀, XY)
(q₁, a, X) -> (q₁, e)
(q₀, a, X) -> (q₁, e)
(q₁, b, Y) -> (q₁, e) Teilmenge von K x V* x G* x K x G*
Übergang von q_i zu q_j
Dabei kann der Automat

lesen,

tilgen,

hinzufügen und

unverändert stehen lassen.

- - Kellerspeicher

G {X, Y} Speicheralphabet

Wie funktioniert das?

Die Abarbeitung der zweiten Hälfte ist leicht zu erkennen: Befindet sich der Automat im Zustand q₁ und repräsentieren im Keller X und Y die Eingabesymbole a und b der linkes Hälfte der Eingabekette in entgegengesetzter Reihenfolge, dann tilgt jedes a ein X und jedes b ein Y aus dem Keller. Findet der Automat ein Eingabesymbol vor, das nicht zum Symbol im Kellerspeicher paßt, oder ist der Kellerspeicher bereits leer, so kann die Eingabe nicht weiter abgearbeitet werden und wird daher nicht akzeptiert. Nur wenn ein Palindrom mit gerader Länge vorliegt, wird der Kellerspeicher vollständig geleert und der Automat befindet sich im Endzustand q₁.

Die erste Hälfte der Eingabe wird dadurch in den Kellerspeicher gebracht, daß dem Kellerspeicher das das Eingabesymbol repräsentierende Symbol hinzugefügt wird, wenn es nicht gerade vom Kellerspeicher gelesen werden kann. Sei die Eingabe z.B. abaaba. Beim Einlesen des zweiten Buchstaben ist im Keller ein X. Daher kann die Regel (q₀, b, X) -> (q₀, XY) angewendet werden. Die Regel (q₀, b, e) -> (q₀, Y) kommt in dieser Situation nicht in Frage, da nach Konvention die leere Kette nur aus dem Kellerspeicher gelesen werden kann, wenn der Speicher leer ist, also nur die leere Kette enthalten ist. Das nächste Zeichen der Eingabe ist ein a. Im Kellerspeicher kann Y gelesen werden, so daß ein weiteres X hinzugefügt wird. Beim folgenden a findet jetzt die Regel (q₀, a, X) Anwendung, und der Automat geht in den Zustand q₁ über. Nun wird der Rest der Folge wie oben beschrieben abgearbeitet.

Bemerkung: Könnte e immer gelesen werden, wären zwar die ersten beiden Regeln gleichbeteutend. Aber wo sonst die vorletzte Regel greifen würde, könnte man auch die erste Regel anwenden. So wäre der Automat nicht mehr deterministisch.

abaaba gehört nicht zur Sprache L. Zwar muß das x in xx^R für den Automaten eine Kette aus abwechselnden a und b sein, aber dafür gibt es mehr Möglichkeiten als die Wiederholung der Kette "ab". Z.B. akzeptiert der Automat neben abaaba auch aa, bb, baab, babbab und babaabab. Die Sprache müßte lauten:
L₃ = { xx^R | x = [b](ab)*[a] }, wobei [] bedeuten sollen, daß der so geklammerte Teil fehlen darf.

Formale Syntaxen für Palindrome

Bisher vorgstellt Sprachen für Palindrome (siehe oben):

L	{ xx^R \| x = (ab)* }	leer Kette, abba, ababbaba, abababbababa usw.
L₂	{ x Î {a, b}* \| x = x^R }	alle Palindrome in V*, also auch z.B. abbaabba und aaaaa
L₃	{ xx^R \| x = [b](ab)*[a] }	Palindrome, in denen außer in der Mitte nie gleiche Buchstaben nebeneinander stehen

Mit den zwei Regeln S -> e und S -> abSba erhält man eine einfache Regelsyntax, die L erzeugt, aber nur von Typ 0 ist. Mit folgender Änderung bekommt man für L eine Typ 1 Syntax: S -> A, A-> abAba und A -> e.
Mit der gleichen Idee, S in der Mitte stehen zu lassen, kann auch eine Syntax für L₂ konstruiert werden: S -> e, S -> aSa, S -> bSb, S -> a und S -> b.
Die Sprache L₃, die obiger Automat akzeptiert, wird von folgender Typ 1 Syntax generiert: S -> A, S -> B, S -> bAb, S -> aBa, A -> e, B -> e, A -> abAba und B -> baBab.

Im Überblick:

L { xx^R | x = (ab)* } S -> e
S -> abSba Typ 0, da
(S -> e) Î R
und S Î y

L₂ { x Î {a, b}* | x = x^R } S -> e
S -> aSa
S -> bSb
S -> a
S -> b Typ 0, da
(S -> e) Î R
und S Î y

L₃ { xx^R | x = [b](ab)*[a] } S -> A
S -> B
A -> bAb
B -> aBa
A -> e
B -> e
A -> abAba
B -> baBab Typ 0, da
lg(A) > lg(e)

Mit kleinen Veränderungen erhält man Syntaxen höhren Typs:

L { xx^R | x = (ab)* } S -> e
S -> A
A -> abba
A -> abAba Typ 1^nr,
Typ 1^e und
Typ 2

L { xx^R | x = (ab)* } S -> e
S -> A
A -> BC
C -> AD
A -> BD
B -> aE
E -> b
D -> bF
F -> a Typ 3,
Normalform,
rechtslinear,
rechtsprädikativ,
allerdings mit
w₂ Î V_N*

L₂ { x Î {a, b}* | x = x^R }

L₃ { xx^R | x = [b](ab)*[a] }

Joachim Wagner
Osnabrück, den 04. Februar 1998

K	{q₀, q₁}	endliche, nicht leere Menge von Zuständen
V	{a, b}	endliche, nicht leere Menge von Eingabesymbolen
s	q₀	Anfangszustand s ÎK
F	{q₀, q₁}	Menge von Endzuständen
D	(q₀, a, e) -> (q₀, X) (q₀, a, Y) -> (q₀, YX) (q₀, b, Y) -> (q₁, e) (q₀, b, e) -> (q₀, Y) (q₀, b, X) -> (q₀, XY) (q₁, a, X) -> (q₁, e) (q₀, a, X) -> (q₁, e) (q₁, b, Y) -> (q₁, e)	Teilmenge von K x V* x G* x K x G* Übergang von q_i zu q_j Dabei kann der Automat lesen, tilgen, hinzufügen und unverändert stehen lassen.
-	-	Kellerspeicher
G	{X, Y}	Speicheralphabet

L	{ xx^R \| x = (ab)* }	S -> e S -> abSba	Typ 0, da (S -> e) Î R und S Î y
L₂	{ x Î {a, b}* \| x = x^R }	S -> e S -> aSa S -> bSb S -> a S -> b	Typ 0, da (S -> e) Î R und S Î y
L₃	{ xx^R \| x = [b](ab)*[a] }	S -> A S -> B A -> bAb B -> aBa A -> e B -> e A -> abAba B -> baBab	Typ 0, da lg(A) > lg(e)

L	{ xx^R \| x = (ab)* }	S -> e S -> A A -> abba A -> abAba	Typ 1^nr, Typ 1^e und Typ 2
L	{ xx^R \| x = (ab)* }	S -> e S -> A A -> BC C -> AD A -> BD B -> aE E -> b D -> bF F -> a	Typ 3, Normalform, rechtslinear, rechtsprädikativ, allerdings mit w₂ Î V_N*
L₂	{ x Î {a, b}* \| x = x^R }

L₃	{ xx^R \| x = [b](ab)*[a] }