Az üres veremmel és végállapottal elfogadó veremautomaták ekvivalenciája

    A veremautomata tehát egy $M=(Q,\Sigma,\Gamma,\delta,q_0,Z_0,F)$ objektum. A kezdo veremszimbólum, Z0, mindig adva van, az elfogadó állapotok halmaza, F, nem mindig. Ha nincs F, (vagy $F=\emptyset$), akkor az automata üres veremmel fogad el. Ezalatt azt értjük, hogy elolvassa a szót és kiuríti a vermet, azaz semmilyen szimbólum, a kezdo veremszimbólum sem lehet a veremben.

    A végállapottal és üres veremmel elfogadó automaták ereje azonos, azaz

    1. Minden végállapottal elfogadó automatához konstruálható vele ekvivalens üres veremmel elfogadó automata, és

    2. minden üres veremmel elfogadó automatához konstruálható vele ekvivalens végállapottal elfogadó automata.

Az 1. állítás konstrukciója vázlatosan a következo.


    Legyen adott egy végállapottal elfogadó $M_1=(Q,\Sigma,\Gamma,\delta,q_0,Z_0,F)$ automata. Konstruáljunk egy ekvivalens üres veremmel elfogadó M2-t.

    $M_2=(Q\cup\{q_e,q_0'\},\Sigma,\Gamma\cup \{X_0\},\delta',q_0',X_0,\emptyset)$, ahol ugye q0' az új kezdoállapot és X0 az új kezdo veremszimbólum.


    $\delta'(q_0',\varepsilon, X_0)=(q_0,Z_0X_0)$,

    $\delta'(q,x,Y)=\delta(q,x,Y),\ q\in Q,\ x\in\Sigma\ or\ x=\varepsilon,\ Y\in\Gamma$,

    $\delta'(q,\varepsilon,Y)=(q_e,\varepsilon),\ q\in F,\ Y\in\Gamma\cup\{X_0\}$,

    $\delta'(q_e,\varepsilon,Y)=(q_e,\varepsilon),\ Y\in\Gamma\cup\{X_0\}$.


A 2. állítás konstrukciója vázlatosan a következo.


    Legyen adott egy üres veremmel elfogadó $M_2=(Q,\Sigma,\Gamma,\delta,q_0,Z_0,\emptyset)$ automata. Konstruáljunk egy ekvivalens végállapottal elfogadó M1-t.

    $M_1=(Q\cup\{q_f,q_0'\},\Sigma,\Gamma\cup \{X_0\},\delta',q_0',X_0,\{q_f\})$, ahol ugye q0' az új kezdoállapot, qf az új elfogadó állapot és X0 az új kezdo veremszimbólum.


    $\delta'(q_0',\varepsilon, X_0)=(q_0,Z_0X_0)$,

    $\delta'(q,x,Y)=\delta(q,x,Y),\ q\in Q,\ x\in\Sigma\ or\ x=\varepsilon,\ Y\in\Gamma$,

    $\delta'(q,\varepsilon,X_0)=(q_f,\varepsilon),\ q\in Q$.