Autómata de pila anidada

Un autómata de pila anidada tiene los mismos dispositivos que un autómata de inserción , pero tiene menos restricciones para su uso.

En la teoría de autómatas , un autómata de pila anidada es un autómata finito que puede hacer uso de una pila que contiene datos que pueden ser pilas adicionales. ^[1] Al igual que un autómata de pila , un autómata de pila anidada puede subir o bajar en la pila y leer el símbolo actual; además, puede en cualquier lugar crear una nueva pila, operar en esa, eventualmente destruirla y continuar operando en la pila anterior. De esta manera, las pilas se pueden anidar recursivamente a una profundidad arbitraria; sin embargo, el autómata siempre opera solo en la pila más interna.

Un autómata de pila anidada es capaz de reconocer un lenguaje indexado , ^[2] y de hecho la clase de lenguajes indexados es exactamente la clase de lenguajes aceptados por los autómatas de pila anidados no deterministas unidireccionales . ^{[1] [3]}

Los autómatas de pila anidados no deben confundirse con los autómatas de inserción integrados , que tienen menos potencia computacional. ^{[ cita requerida ]}

Definición formal

Autómata

Un autómata de pila anidada (no determinista bidireccional) es una tupla ⟨ Q ,Σ,Γ,δ, q ₀ , Z ₀ , F ,[,], ] ⟩ donde

• Q , Σ y Γ son un conjunto finito no vacío de estados, símbolos de entrada y símbolos de pila, respectivamente,
• [, ] y ] son ​​símbolos especiales distintos que no están contenidos en Σ ∪ Γ,
  • [ se utiliza como marcador final izquierdo tanto para la cadena de entrada como para una cadena de (sub)pila,
  • ] se utiliza como marcador final derecho para estas cadenas,
  • ] se utiliza como marcador final de la cadena que denota toda la pila. ^{[nota 1]}
• Un alfabeto de entrada extendido se define por Σ' = Σ ∪ {[,]}, un alfabeto de pila extendido por Γ' = Γ ∪ {]}, y el conjunto de direcciones de movimiento de entrada por D = {-1,0,+1}.
• δ, el control finito, es una aplicación de Q × Σ' × (Γ' ∪ [Γ' ∪ { ] , [ ] }) en subconjuntos finitos de Q × D × ([Γ ^* ∪ D ), tales que δ se asigna ^{[nota 2]}

De manera informal, el símbolo superior de una (sub)pila junto con su marcador final izquierdo precedente "[" se considera como un solo símbolo; ^[4] entonces δ se lee

• El estado actual,
• el símbolo de entrada actual, y
• el símbolo de pila actual,

y salidas

• El siguiente estado,
• la dirección en la que moverse en la entrada, y
• la dirección en la que moverse en la pila, o la cadena de símbolos para reemplazar el símbolo superior de la pila.

• q ₀ ∈ Q es el estado inicial,
• Z ₀ ∈ Γ es el símbolo de pila inicial,
• F ⊆ Q es el conjunto de estados finales.

Configuración

Una configuración , o descripción instantánea de tal autómata, consiste en una triple ⟨ q , [ a ₁ a ₂ ... a _i ... a _{n -1} ], [ Z ₁ X ₂ ... X _j ... X _{m -1} ] ⟩ , donde

• q ∈ Q es el estado actual,
• [ a ₁ a ₂ ... a _i ... a _{n -1} ] es la cadena de entrada; para mayor comodidad, se define a ₀ = [ y a _n ^{= ] [nota 3]} La posición actual en la entrada, es decir, i con 0 ≤ i ≤ n , se marca subrayando el símbolo respectivo.
• [ Z ₁ X ₂ ... X _j ... X _{m -1} ] es la pila, incluidas las subpilas; por conveniencia, se define X ₁ = [ Z ₁ ^{[nota 4]} y X _m = ] . La posición actual en la pila, es decir, j con 1 ≤ j ≤ m , se marca subrayando el símbolo respectivo.

Ejemplo

Un ejemplo de ejecución (cadena de entrada no mostrada):

Propiedades

Cuando se permite a los autómatas volver a leer su entrada (" autómatas bidireccionales "), las pilas anidadas no dan como resultado capacidades de reconocimiento de lenguaje adicionales, en comparación con las pilas simples. ^[5]

Gilman y Shapiro utilizaron autómatas de pila anidada para resolver el problema de palabras en ciertos grupos . ^[6]

Notas

1. Aho originalmente usaba "$", "¢" y "#" en lugar de "[", "]" y " ] ", respectivamente. Véase Aho (1969), p.385 arriba.
2. La yuxtaposición denota una concatenación de cadenas (conjuntos) y tiene una prioridad de enlace más alta que la unión de conjuntos ∪. Por ejemplo, [Γ' denota el conjunto de todas las cadenas de longitud 2 que comienzan con "[" y terminan con un símbolo de Γ'.
3. Originalmente, Aho usaba los marcadores de pila izquierdo y derecho, es decir, $ y ¢, como marcadores de entrada derecho e izquierdo, respectivamente.
4. El símbolo superior de una (sub)pila junto con su marcador final izquierdo precedente "[" se considera un solo símbolo.

Referencias

1. Aho, Alfred V. (julio de 1969). "Autómatas de pila anidada". Revista de la ACM . 16 (3): 383–406. doi : 10.1145/321526.321529 . S2CID  685569.
2. Partee, Barbara ; Alice ter Meulen ; Robert E. Wall (1990). Métodos matemáticos en lingüística . Kluwer Academic Publishers. págs. 536–542. ISBN 978-90-277-2245-4.
3. John E. Hopcroft, Jeffrey D. Ullman (1979). Introducción a la teoría de autómatas, lenguajes y computación . Addison-Wesley. ISBN 0-201-02988-X.Aquí:p.390
4. Aho (1969), pág. 385 arriba
5. Beeri, C. (junio de 1975). "Los autómatas de pila anidados de dos vías son equivalentes a los autómatas de pila de dos vías". Journal of Computer and System Sciences . 10 (3): 317–339. doi : 10.1016/s0022-0000(75)80004-3 .
6. Shapiro, Robert Gilman Michael (4 de diciembre de 1998). Sobre grupos cuyo problema verbal se resuelve mediante un autómata de pila anidada (informe técnico). arXiv : math/9812028 . CiteSeerX 10.1.1.236.2029 . S2CID  12716492.