Zur Haupt­na­vi­ga­ti­on sprin­gen [Alt]+[0] Zum Sei­ten­in­halt sprin­gen [Alt]+[1]

Kel­ler­au­to­ma­ten (neu im BP: Item 13)

Stackautomat für die Erkennung von Klammerpaaren ohne Inhalt

Ab­bil­dung 5: Stack­au­to­mat für die Er­ken­nung von Klam­mer­paa­ren ohne In­halt; a steht für "Klam­mer auf" und z für "zu"; das Zei­chen # für einen lee­ren Stack. Ach­tung: Die Skiz­ze ver­wen­det die bes­ser les­ba­re Syn­tax (#, push, pop), die JFLAP aber nicht aus­füh­ren kann! ZPG In­for­ma­tik [CC BY-SA 4.0 DE], aus zpg_­spra­chen­au­to­ma­ten_hin­ter­grund.odt

Ein Kel­ler­au­to­mat16 ist ein nor­ma­ler DEA, der neben sei­nen Zu­stän­den und Über­gän­gen auch einen Kel­ler­spei­cher, also einen LIFO-(last in, first out) Spei­cher be­sitzt. Der Kel­ler­au­to­mat kann

  1. jede Tran­si­ti­on zu­sätz­lich vom obers­ten Ele­ment des Stack ab­hän­gig ma­chen und
  2. bei jeder Tran­si­ti­on auch den Stack ma­ni­pu­lie­ren, also einen zu­sätz­li­chen Wert dar­auf­le­gen (PUSH17 ), den obers­ten Wert ent­neh­men (POP) oder den Stack un­ver­än­dert las­sen (NOP).

Der ent­schei­den­de Un­ter­schied zum DEA ist hier der un­be­grenz­te Spei­cher­platz auf dem Stack.

Wäh­rend DEAs Klam­mer­spra­chen nicht er­ken­nen kön­nen, ist an­schau­lich klar, wie ein Kel­ler­au­to­mat die­ses Pro­blem löst: Er be­ginnt mit lee­rem Stack und legt bei jeder öff­nen­den Klam­mer ein Sym­bol (z.B. „k“ für Klam­mer) dar­auf ab. Bei jeder schlie­ßen­den Klam­mer ent­fernt er eines; die An­zahl der „k“ auf dem Stack zählt also die mo­men­ta­ne Klam­me­rungs­tie­fe; das Ent­fer­nen vom lee­ren Stack führt zu einem Feh­ler. Der Au­to­mat für diese Auf­ga­be muss in einem End­zu­stand ste­hen (und das Wort damit ak­zep­tie­ren), falls am Ende der Ein­ga­be auch der Stack leer ist.

Bild 5 zeigt einen ein­fa­chen Kel­ler­au­to­ma­ten, der Klam­mer­aus­drü­cke er­kennt. Vom Input wer­den hier nur die Klam­mern selbst be­trach­tet und ihr „In­halt“ igno­riert; zu­guns­ten der Les­bar­keit ver­wen­den wir au­ßer­dem a und z statt „Klam­mer-auf“ und „-zu“. Kor­rekt ge­klam­mer­te Aus­drü­cke sind also etwa az, aaazzz, azaz oder aa­zazz. Wie schon an­ge­spro­chen gilt auch das leere Wort als kor­rekt ge­klam­mert.

Im Über­gangs­gra­phen be­deu­tet die Tran­si­ti­on (a, k; push k) Fol­gen­des: „FALLS im Zu­stand q1 das Ein­ga­be­zei­chen a an­liegt UND auf dem Stack ein k liegt, DANN wechs­le in Zu­stand q1 und push ein wei­te­res k“. Das Zei­chen # steht für einen lee­ren Stack, das λ für „kein Eingabe­zeichen“ (Merk­hil­fe: lamb­da für „leer“, oft auch ep­si­lon für „empty“). Diese Tran­si­ti­on ver­braucht also keine Ein­ga­be.

Um Kel­ler­au­to­ma­ten im Un­ter­richt aus­führ­li­cher zu be­han­deln, muss man eine über­sicht­li­che Dar­stel­lung für deren Be­schrei­bung wäh­len, denn ihre Tran­si­ti­ons­ta­bel­le ist (an­ders als die eines DEA) lei­der drei­di­men­sio­nal, da die Über­gän­ge a) vom ak­tu­el­len Zu­stand, b) vom Ein­ga­be­zei­chen und c) auch noch vom Zei­chen auf dem Stack ab­hän­gen. Oben­drein ent­hält jede Tran­si­ti­on den Nach­fol­ge­zu­stand und eine Stack­ope­ra­ti­on. Auch ein „Lauf“ des Au­to­ma­ten ist auf­wän­di­ger zu pro­to­kol­lie­ren als bei einem DEA (siehe Seite 12).

Hin­weis zu Item 13 des Bil­dungs­plans

Der Bil­dungs­plan Ab­schnitt „3.3.5 Au­to­ma­ten und for­ma­le Spra­chen“ ent­hält in Item 13 die For­mu­lie­rung „kon­text­freie Spra­chen durch Kel­ler­au­to­ma­ten und kon­text­freie Gram­ma­ti­ken be­schrei­ben“. Sie ist so zu ver­ste­hen, dass Schü­le­rin­nen

  • kon­text­freie Spra­chen durch kon­text­freie Gram­ma­ti­ken be­schrei­ben
  • und damit auch Her­lei­tun­gen durch­füh­ren (also Wort­pro­ble­me lösen) kön­nen.

Kel­ler­au­to­ma­ten wer­den nur als Er­wei­te­rung von DEA be­han­delt, weil sie auch kontext­freie Spra­chen er­ken­nen kön­nen. Man muss daher...

  • die prin­zi­pi­el­le Ar­beits­wei­se eines Kel­ler­au­to­ma­ten bei der Er­ken­nung einer ge­ge­be­nen Spra­che be­schrei­ben kön­nen,
  • die Be­schrei­bung eines Kel­ler­au­to­ma­ten (der als Zu­stands­über­gangs­dia­gramm oder in einer for­ma­len Dar­stel­lung ge­ge­ben ist) in­ter­pre­tie­ren und er­läu­tern sowie einen Lauf die­ses Au­to­ma­ten pro­to­kol­lie­ren kön­nen, …
… Kel­ler­au­to­ma­ten (an­ders als DEAs) aber nicht de­tail­liert kon­stru­ie­ren.

For­ma­le Dar­stel­lung eines Kel­ler­au­to­ma­ten

Eine for­ma­le und voll­stän­di­ge Be­schrei­bung des Kel­ler­au­to­ma­ten aus Ab­bil­dung 5 um­fasst...

… all­ge­mein: … im Bei­spiel:
das Ein­ga­be­al­pha­bet ∑ ∑ = {a, z}
eine Menge Z von Zu­stän­den Q = {q0,q1,qF} (incl. Feh­ler­zu­stand!)
den Start­zu­stand s ∈ Z s = q0
eine Menge E ⊆ Z von End­zu­stän­den E = {q0}
das Stack­al­pha­bet Γ (Gamma) Γ ={#, k}; das # steht für einen lee­ren Stack
und die Über­gangs­funk­ti­on δ: Q ⊗ ∑ ⊗ Γ → S ⊗ {push, pop, nop}, die hier von drei Kri­te­ri­en ab­hängt und des­we­gen zei­len­wei­se an­ge­ge­ben wer­den muss:
Kri­te­ri­en Aus­wir­kung
alter Zu­stand? Ein­ga­be? auf Stack? neuer Zu­stand Ope­ra­ti­on
0 a # 1 push k
1 a k 1 push k
1 z k 1 pop k
1 λ # 0 nop
Alle an­de­ren Tran­si­tio­nen füh­ren in den Feh­ler­zu­stand. Weil drei Kri­te­ri­en sehr viele Mög­lich­kei­ten auf­span­nen, wird für die Über­gangs­ta­bel­le eines Kel­ler­au­to­ma­ten (an­ders als beim DEA!) auf die voll­stän­di­ge Auf­lis­tung die­ser Tran­si­tio­nen ver­zich­tet.

Ab­lauf­pro­to­koll eines Kel­ler­au­to­ma­ten

Ähn­lich wie ein Schreib­tisch­test den Ab­lauf eines Pro­gramms do­ku­men­tiert, kann auch der „Lauf“ eines Kel­ler­au­to­ma­ten do­ku­men­tiert wer­den, wobei die durch­lau­fe­nen Zu­stän­de, die Ent­wick­lung des Stack und das Ver­brau­chen der Ein­ga­be sicht­bar wer­den soll­ten. Dazu eig­net sich bei­spiels­wei­se die Dar­stel­lung wie in Ta­bel­le 1.

Ta­bel­le 1: Ab­lauf­pro­to­koll des Kel­ler­au­to­ma­ten aus Ab­bil­dung 5 für die Ein­ga­be aa­zazz

Stack ↑
k k
k k k k k
# # # # # # # #
Zu­stand q0 q1 q1 q1 q1 q1 q1 q0
Vom Über­gang ver­brauch­tes Ein­gabe­zei­chen a a z a a z Ein­ga­be endet, q0 ist End­zu­stand: Wort wird ak­zep­tiert!

Die an­ge­deu­te­ten Ko­or­di­na­te­n­ach­sen span­nen dabei nach oben die Höhe des Sta­pels, nach rechts die Zeit auf; im Dia­gramm sieht man, wie er mehr­fach wächst und schrumpft. Unter der Recht­sach­se wird der je­weils er­reich­te Zu­stand no­tiert und in der letz­ten Zeile das Ein­ga­be­zei­chen, das der je­wei­li­ge Zu­stands­über­gang ver­braucht hat.

Auf­merk­sa­me Schü­ler könn­ten be­mer­ken, dass die Ein­ga­be endet, wäh­rend der Au­to­mat noch in Zu­stand q1 steht – also nicht in einem End­zu­stand! Trotz­dem ak­zep­tiert er die Ein­ga­be, weil der letz­te Über­gang (von q1 nach q0) ohne Vor­lie­gen oder Ver­brau­chen eines Ein­ga­be­zei­chens statt­findet. Die­ser Über­gang mutet in­so­fern „etwas nicht­de­ter­mi­nis­tisch“ an. Den­noch wird ein sol­cher Au­to­mat als de­ter­mi­nis­tisch be­zeich­net18 , so­fern zwi­schen den Tran­si­tio­nen mit Eingabe­zeichen (zwei­te und drit­te Zeile der Über­gangs­ta­bel­le, Ein­ga­be a bzw. z) und denen mit λ (vier­te Zeile) keine Mehr­deu­tig­kei­ten auf­tre­ten.

Was Kel­ler­au­to­ma­ten kön­nen (BP: Item 14)

Wie in der Ta­bel­le auf Seite 3 schon be­schrie­ben , er­ken­nen Kel­ler­au­to­ma­ten genau die kontext­freien Spra­chen. Zwar wer­den diese eben­so durch kon­text­freie Gram­ma­ti­ken oder Syntax­diagramme be­schrie­ben; für die Klä­rung, wel­che Spra­chen denn kon­text­frei sind und wel­che nicht, könn­te man also auch letz­te­re her­an­zie­hen. Die An­schau­ung eines Sta­pels und wie der Au­to­mat ihn wäh­rend der Er­ken­nung suk­zes­si­ve auf- und ab­baut, ist aber bes­ser nach­voll­zieh­bar, wes­we­gen wir für schon für die Klam­mer­spra­chen damit ar­gu­men­tiert haben.

Spra­che kann von PDA er­kannt wer­den Be­grün­dung
L = {an zn : n∈ℕ} ja ist ein Spe­zi­al­fall der Klam­mer­spra­che
L = {an bm cn : m, n∈ℕ} ja Stack wird mit den a be­la­den, dann alle b lesen (An­zahl un­er­heb­lich), dann Stack über die c wie­der ent­la­den
L = {ak bm cn : k, m, n∈ℕ} ja Diese Spra­che kann sogar von einem DEA er­kannt wer­den (die An­zah­len der a, b und c müs­sen ja gar nicht über­ein­stim­men, so dass der Au­to­mat sie auch nicht zäh­len muss), also erst recht von einem Kel­ler­au­to­ma­ten.
L = {an bn cn : n∈ℕ} nein Der Au­to­mat müss­te die a ein­le­sen und dabei den Stack be­la­den. Für die Zäh­lung der b muss er ihn an­schlie­ßend wie­der ent­la­den (denn nur auf diese Weise kann er zäh­len). Da­nach ist der Stack leer, er hat die An­zahl „ver­ges­sen“ und kann daher die c nicht mehr zäh­len. Mit zwei Stacks würde es al­ler­dings gehen.
L = Menge aller Vor­na­men der deut­schen Spra­che ja Diese Spra­che ent­hält so­wie­so nur end­lich viele Wör­ter. Damit kann sie sogar von einem DFA er­kannt wer­den, also erst recht von einem Kel­ler­au­to­ma­ten.
XML-ar­ti­ge Spra­chen mit vor­her fest­ge­leg­ten Tags ja (siehe Ab­bil­dung 6)
all­ge­mei­nes XML nein (siehe Ab­bil­dung 6)
Java nein (siehe unten)
N

Ab­bil­dung 6: Prin­zip­skiz­ze eines XML-Do­ku­ments mit ge­schach­tel­ten Tags ZPG In­for­ma­tik [CC BY-SA 4.0 DE], aus zpg_­spra­chen­au­to­ma­ten_hin­ter­grund.odt

Das Bei­spiel in Ab­bil­dung 6 zeigt, dass bei XML-ar­ti­gen Spra­chen die öff­nen­den <...> und schlie­ßen­den </...> Tags eine klam­mer­ar­tig ge­schach­tel­te Struk­tur bil­den. Falls die er­laub­ten Tags von vorn­her­ein fest­ge­legt sind (in HTML z.B. <table>, <p>, <title> usw.), kann man für die Er­ken­nung eine Kel­ler­ma­schi­ne kon­stru­ie­ren: Ihr Sta­pel­al­pha­bet Γ muss dann für jedes be­kann­te Tag einen „Tag-Code“ ent­hal­ten, der bei Auf­tre­ten die­ses Tags auf den Stack ge­legt wird. An­hand der schlie­ßen­den Tags in der Ein­ga­be kann der Au­to­mat den Stack dann pas­send wie­der ab­bau­en und dabei über­prü­fen, ob das in der Ein­ga­be ge­ra­de ge­schlos­se­ne Tag auch das ist, das zu­letzt auf dem Sta­pel ge­spei­chert wor­den war.

Falls die er­laub­ten Tags hin­ge­gen nicht im Vor­aus fest­ge­legt sind (und bei all­ge­mei­nem XML sind sie eben nicht fest­ge­legt), ist die Si­tua­ti­on schwie­ri­ger: Weil das Stack­al­pha­bet nicht pas­send er­wei­tert wer­den kann, könn­te der Au­to­mat die öff­nen­den Tags al­len­falls zei­chen­wei­se auf den Stack legen. Wenn er dann aber ein schlie­ßen­des Tag an­trifft und des­sen Zei­chen (vor­wärts!) aus der Ein­ga­be liest, kann er sie nicht mit dem Tag ab­glei­chen, des­sen Zei­chen nur rück­wärts vom Stack ge­le­sen wer­den kön­nen. Wie schon bei DEA kann auch die­ses Pro­blem wie­der nicht durch eine end­li­che Zahl zu­sätz­li­cher Zu­stän­de ge­löst wer­den, wenn die Tags be­lie­big lang sein dür­fen.

Auch Java oder ähn­li­che Pro­gram­mier­spra­chen kann eine Stack­ma­schi­ne nicht er­ken­nen. Für die Be­grün­dung ar­gu­men­tiert man al­ler­dings nicht mit dem Stack, son­dern ausnahms­weise mit der zu­ge­hö­ri­gen kon­text­frei­en Gram­ma­tik (ab Seite 19): Man be­trach­tet ein Frag­ment wie

1   public void fehlerhaft() {
2      int k = 12;
3      m = k + 1;
4   }
in dem die nicht de­kla­rier­te Va­ria­ble m in Zeile 3 einen Com­pi­l­er­feh­ler aus­löst, ob­wohl die Zu­wei­sung doch grund­sätz­lich rich­tig ge­schrie­ben ist. Als recht in­for­mel­le Be­grün­dung soll hier rei­chen, dass die Kor­rekt­heit der Zeile in einem Kon­text be­ur­teilt wer­den muss, der über diese Zeile und sogar über die be­trach­te­te Me­tho­de hin­aus­geht (hier ab­hän­gig von vor­her de­kla­rier­ten Va­ria­blen und At­tri­bu­ten). Diese Ab­hän­gig­keit kann eine kon­textfreie Gram­ma­tik aber nicht aus­drü­cken, so dass ein Kel­ler­au­to­mat die Spra­che auch nicht er­ken­nen kann.

 

16 Ein Kel­ler wird oft Sta­pel oder (auch im Deut­schen) Stack ge­nannt, für Kel­ler­au­to­ma­ten sind „Stack­au­to­mat“ oder PDA („push­down au­to­ma­ton“) ge­bräuch­lich.

17 Hin­weis: Hier wurde eine über­sicht­li­che­re Schreib­wei­se mit PUSH, POP und NOP ver­wen­det, die aber zu JFLAP nicht kom­pa­ti­bel ist. JFLAP er­laubt es (lei­der) sogar, das Zei­chen # noch vom lee­ren Stack zu POPen, der an­schlie­ßend „ganz leer“ ist. Da sie für die Er­fül­lung des Bil­dungs­plans nicht er­for­der­lich ist, emp­feh­len wir, auf die prak­ti­sche Ar­beit mit PDAs in JFLAP zu ver­zich­ten.

18 Quel­le z.B. https://​de.​wi­ki­pe­dia.​org/​wiki/​Kel​lera​utom​at#​For­ma­le_​De­fi­ni­ti­on “Wenn die Über­gangs­funk­ti­on die Ei­gen­schaft ∀ z∈Z , ∀ a∈Σ , ∀ g∈Γ , | δ ( z , a , g ) | + | δ ( z , ε , g ) | ≤ 1 er­füllt, spricht man von einem de­ter­mi­nis­ti­schen Kel­ler­au­to­ma­ten. Zu einer fes­ten Ein­ga­be gibt es dann höchs­tens eine Zu­stands­über­gangs­ab­fol­ge, Mehr­deu­tig­kei­ten kön­nen also nicht auf­tre­ten.“

 

Hin­ter­grund­in­for­ma­tio­nen: Her­un­ter­la­den [odt][669 KB]

 

Wei­ter zu Tu­ring­ma­schi­nen