9. Veremautomaták

• 9. Veremautomaták
  • Veremautomata konfigurációi
  • Egylépéses redukció
  • Többlépéses redukció és a felismert nyelv
  • Determinisztikus veremautomata
  • Üres veremmel felismert nyelv
  • Végállapottal vs üres veremmel elfogadás
  • Veremautomaták és környezetfüggetlen grammatikák
  • Források

• Input szalag

• Verem

• Véges vezérlő

• A veremautomata a véges automata általánosítása potenciálisan végtelen veremmel és véges kontrollal.

• A verem esetében az új adat mindig a már meglév˝o veremtartalom tetejéhez adódik, kivétele fordított sorrendben történik.

• alapértelmezetten nemdeterminisztikus

A veremautomata egy $A=⟨Z,Q,\Sigma ,\delta ,z_0,q_0,F⟩$ rendezett hetes, ahol

• $Z$ a veremszimbólumok véges halmaza

• $Q$ az állapotok véges halmaza

• $\Sigma$ az inputszimbólumok véges halmaza

• $\delta :Z\times Q\times (\Sigma \cup \{ϵ\})\to {\mathcal{P}}_{v\acute{e}ges}(Z^{\ast }\times Q)$ az úgynevezett átmeneti függvény

• $z_0\in Z$ a kezdeti veremszimbólum

• $q_0\in Q$ a kezdeti állapot

• $F\subseteq Q$ az elfogadó állapotok vagy végállapotok halmaza

• A verem tetején lévő szimbólum, az aktuális állapot és az inputszimbólum együttesen határozzák meg a következő átmenetet.

• Minden lépésben mindenképpen kiveszünk egyetlen egy elemet a verem tetejéről és beteszünk helyette néhányat. (0, 1, 2, $\dots$ darabot)

• Ha $\delta (z,q,\sigma )$ nem üres, akkor ún. $\sigma$-átmenet hajtható végre, ami lehetővé teszi, hogy a veremautomata anélkül változtassa meg az állapotát és/vagy a verem tartalmát, hogy az inputszalagról betűt olvasna be.

• $ϵ$-mozgásra lehetőség van már az első inputszimbólum elolvasása előtt is illetve még az utolsó inputszimbólum elolvasása után is.

Veremautomata konfigurációi

A veremautomata konfigurációja alatt egy $zqw$ alakú szót értünk, ahol $z\in Z^{\ast }$ a verem aktuális tartalma és $q\in Q$ az aktuális állapot és $w\in {\Sigma }^{\ast }$ az input még feldolgozatlan része.

Kezdőkonfigurácicó: $z_0{q}_{0}w$

Egylépéses redukció

Az $A$ veremautomata az $\alpha \in Z^{\ast }Q{\Sigma }^{\ast }$ konfigurációt a $\beta \in Z^{\ast }Q{\Sigma }^{\ast }$ konfigurációra redukálja egy lépésben, amelyet $\alpha ⟹\beta$-val jelölünk, ha létezik olyan $z\in Z,q,p\in Q,a\in \Sigma \cup \{\sigma \},r,u\in Z^{\ast }$ és $w\in {\Sigma }^{\ast }$ , hogy $(u,p)\in \delta (z,q,a)$ és $\alpha =rzqaw$ és $\beta =rupw$ teljesül.

Többlépéses redukció és a felismert nyelv

Az $A$ veremautomata az $\alpha \in Z^{\ast }Q{\Sigma }^{\ast }$ konfigurációt a $\beta \in Z^{\ast }Q{\Sigma }^{\ast }$ konfigurációra redukálja, amelyet $\alpha ⟹\beta$-val jelöljük, ha vagy $\alpha =\beta$, vagy létezik olyan ${\alpha }_1,\dots ,{\alpha }_n$ szavakból álló véges sorozat, ahol $\alpha ={\alpha }_1,\beta ={\alpha }_n$ és ${\alpha }_i⟹{\alpha }_{i+1}$

Az $A$ veremautomata által elfogadó állapottal felismert nyelv: $$L(A)=\{w\in {\Sigma }^{\ast }|z_0{q}_{0}w⟹up,\mathrm{ahol}u\in Z^{\ast },p\in F\}$$

Determinisztikus veremautomata

Az $A$ veremautomatát determinisztikusnak nevezünk, ha minden $(z,q,a)\in Z\times Q\times \Sigma$ esetén $|\delta (z,q,a)|+|\delta (z,q,ϵ)|=1$

Tehát minden $q\in Q$ és $z\in Z$ esetén

• vagy $\delta (z,q,a)$ pontosan egy elemt tartalmaz, minden $a\in \Sigma$ inoutszimbólumra és $\delta (z,q,ϵ)=\varnothing$
• vagy $\delta (z,q,ϵ)$ pontosan egy elemet tartalmaz és $\delta (z,q,a)=\varnothing$ minden $a\in \Sigma$ inputszimbólumra.

Üres veremmel felismert nyelv

Az $A$ veremautomata által üres veremmel felsimert nyelv: $$N(A)=\{w\in {\Sigma }^{\ast }|z_0{q}_{0}w⟹p\mathrm{ahol}p\in Q\}$$

Vegyük észre, hogy ha a verem üres, akkor az automata működése blokkolódik, mivel nincs átmenet definiálva üres verem esetére.

Így a verem az input teljes feldolgozása után, az utolsó átmenettel kell üressé váljon.

Szintén a blokkolás elkerülése végett definiáltuk úgy a kezdőkonfigurációt, hogy a veremábécé egy eleme ($z_0$) már eleve a veremben van.

Az elfogadó állapotok halmaza irreleváns $N(A)$ szempontjából.

Végállapottal vs üres veremmel elfogadás

Bármely $A$ veremautomatához meg tudunk adni egy $A^{\prime }$ veremautomatát, úgy, hogy $N(A^{\prime })=L(A)$ teljesül

Bármely $A$ veremautomatához meg tudunk adni egy $A^{\prime }$ veremautomatát, úgy, hogy $L(A^{\prime })=N(A)$ teljesül

Veremautomaták és környezetfüggetlen grammatikák

Bármely $G$ környezetfüggetlen grammatikához magkonstruálható egy olyan $A$ veremautomata, amelyre $L(A)=L(G)$ teljesül.

Minden $A$ veremautomatához megadható egy környezetfüggetlen $G$ grammatika úgy, hogy $L(G)=N(A)$ teljesül

Források

• Diasor
• Felvétel