Una forma natural de aumentar el poder computacional de nuestra AP es aumentar el número de pilas, en particular podemos agregar una más en el denominado Autómata de Doble Pila
ADP #
Un Autómata de Doble Pila (ADP) es una tupla
\((Q,\Sigma,\Gamma,q_0,Z_0,A, \delta )\)
donde:
- \(Q\) es un conjunto de estados finitos
- \(\Sigma\) es un alfabeto de símbolos terminales
- \(\Gamma\) es un alfabeto de la pila
- \(q_0\) es un estado que denominaremos inicial donde \(q_0 \in Q\)
- \(Z_0\) es un símbolo de la pila que denominaremos inicial de la pila donde \(Z_0 \in \Gamma\)
- \(A\) es un conjunto de estados que denominaremos finales donde \(A \subset Q\)
- \(\delta\) es una función de transición que cumple con: \[\delta:Q \times (\Sigma\cup \{\varepsilon\}) \times \Gamma \times \Gamma \rightarrow Q \times \Gamma^* \times \Gamma^* \]
Ejemplo de ADP #
El siguiente autómata reconoce al lenguaje formado de cadenas \(a^nb^nc^n\) para cuando n>0:
ADP para cadenas aⁿbⁿcⁿ con n>0
Al igual que con los AF, al comenzar el análisis se comienza en el estado inicial y de ahí se tienen que poner atención a cuatro aspectos, el estado en el que se está, el símbolo en la cadena que está siendo analizado, el símbolo que se encuentra hasta arriba de la primer pila y el símbolo que se encuentra hasta arriba de la segunda pila.
