8.5. Árnyék-veremautomata

Ahogy az eredeti legbaloldalibb levezetés alapján a veremautomatát megkonstruálhattuk, úgy készítjük el az árnyék-veremautomatát a környezetfüggő legbaloldalibb levezetés esetére. Az árnyék-veremautomata vermében a hagyományos veremszimbólumok mellett, árnyékszimbólumok is lehetnek. Az automata olvashat a szalagról egy betűt, látja a veremben levő legfelső veremszimbólumot, illetve a közvetlenül ezen levő árnyékszimbólumhoz is hozzáférhet.

22. Definíció. Az (állapotnélküli nemdeterminisztikus) árnyék-veremautomata egy S P D A=(T, ZZ ', X 0, d) rendezett négyes, ahol T az input ábécé, Z a veremábécé, Z '={X ' | XZ} az árnyékszimbólumok halmaza, X 0 a kezdő veremszimbólum, d:(T∪{λ})×Z×Z ' → (ZZ ')* pedig az átmenetfüggvény; ahol a d átmenetfüggvény a következő átmeneteket írhatja le:

- λ, A '∈d(a, A, λ), ez az átmenet csak akkor lehetséges ha nincs árnyékszimbólum az A felett a veremben, ekkor az automata elolvassa az a- t a szalagról és törli a verem tetején levő A- t, vagy kicseréli az árnyékára ( A ' ).

- B C, B C A '∈d(λ, A, λ), ezekben az átmenetekben az A- ra rátesszük a C- t és a B- t (a B lesz a legfelső veremszimbólum), és az A- t töröljük, vagy az árnyékára cseréljük.

- C, C B ', A 'C, A 'C B '∈d(λ, B, A '), ezekben az átmenetekben az A ' árnyékszimbólumnak pont a legfelső verem szimbólumon, B- n kell lennie; ekkor B- re rátesszük a C- t (a C lesz a legfelső veremszimbólum) és a B- t töröljük, vagy az árnyékára cseréljük, illetve az A '- t is törölhetjük. ★

Az árnyék-veremautomata egy konfigurációja (w, z), ahol wT * a még feldolgozandó input, z∈(ZZ ')* pedig a verem aktuális tartalma. Akkor fogadunk el egy w szót, ha a (w, X 0) konfigurációból a megadott átmenetek alapján véges sok lépésben elérhető a (λ, λ) konfiguráció, vagyis elfogy az input és a verem kiürül. Belátható, hogy az automata a Penntonen normálforma alapján értelmezett legbaloldalibb levezetést szimulálja, így bizonyítható a következő tétel.

66. Tétel. Az állapotnélküli nemdeterminisztikus árnyék-veremautomaták pontosan a környezetfüggő nyelvek osztályát fogadják el.

8.12. példa - Árnyék-veremautomata és működése

Legyen SPDA=({a,b,c},{S,A,B,C,D,E,F,G,I,J,K,L,M,O}∪ {S',A',B',C',D',E',F',G',I',J',K',L',M',O'}, S, d), ahol d a következőképpen definiált:



 
            λ,A' ∈d(a,A, λ),
 λ,B' ∈d(b,B, λ),
 λ,C' ∈d(c,C, λ),
 λ,D' ∈d(a,D, λ),
 λ,E' ∈d(b,E, λ),
 λ,F' ∈d(c,F, λ),
 λ,I' ∈d(a,I, λ),
 λ,L' ∈d(c,L, λ),
 AG,AGS' ∈d(λ,S, λ),
 BC,BCG' ∈d(λ,G, λ),
 IJ,IJA' ∈d(λ,A, λ),
 DE,DEJ' ∈d(λ,J, λ),
 FL,FLK' ∈d(λ,K, λ),
 IM,IMD' ∈d(λ,D, λ),
 AB,ABM' ∈d(λ,M, λ),
 CL,CLO' ∈d(λ,O, λ),
 E,EB',E'E,E'EB' ∈d(λ,B, E'),
 K,KC',E'K,E'KC' ∈d(λ,C, E'),
 B,BE',B'B,B'BE' ∈d(λ,E, B'),
 O,OF',B'O,B'OF' ∈d(λ,F, B').
 

Ekkor az aaabbbccc input szón lehetséges az SPDA következő futása: a konfigurációkat adjuk meg, az árnyékszimbólumokat (piros és lila), illetve az átmenetfüggvényben felhasznált inputbetűket (kék) és a verem tetején felhasznált betűket (kék veremszimbólum, illetve lila árnyékszimbólum) emeltük ki.

Ez alapján a szót az automata elfogadja. ★