Hispanopedia Wiki
Articulo de referencia

Autómata de pila anidada

Un autómata de pila anidada tiene los mismos dispositivos que un autómata de pila , pero tiene menos restricciones para su uso. En la teoría de autómatas , un autómata de pila a...

Hispanopedia WikiContenido en espanolLectura gratuita
Un autómata de pila anidada tiene los mismos dispositivos que un autómata de pila , 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 utilizar 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 crear una nueva pila en cualquier lugar, operar sobre ella, destruirla y continuar operando sobre la pila anterior. De esta manera, las pilas pueden anidarse recursivamente a una profundidad arbitraria; sin embargo, el autómata siempre opera solo sobre la pila más interna.

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

Los autómatas de pila anidados no deben confundirse con los autómatas de pila incrustados , que tienen menor capacidad de cálculo.

Definición formal

Autómata

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

  • Q , Σ y Γ son, respectivamente, un conjunto finito no vacío de estados, símbolos de entrada y símbolos de pila.
  • [, ], y ] son ​​símbolos especiales distintos que no están contenidos en Σ ∪ Γ,
    • [ se utiliza como marcador de extremo izquierdo tanto para la cadena de entrada como para una cadena de (sub)pila,
    • ] se utiliza como marcador de extremo 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 ), de tal manera que δ aplica [ nota 2 ]
De manera informal, el símbolo superior de una (sub)pila junto con su marcador de extremo izquierdo precedente "[" se considera 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 resultados
  • el siguiente estado,
  • la dirección en la que moverse según 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 0 ∈ Q es el estado inicial,
  • Z 0 ∈ Γ 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 dicho autómata, consiste en una tripleta ⟨ q , [ a 1 a 2 ... a i ... a n -1 ], [ Z 1 X 2 ... X j ... X m -1 ] ⟩ , donde

  • q ∈ Q es el estado actual,
  • [ a 1 a 2 ... a i ... a n -1 ] es la cadena de entrada; para mayor comodidad, se define a 0 = [ 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 correspondiente.
  • [ Z 1 X 2 ... X j ... X m -1 ] es la pila, incluyendo las subpilas; para mayor comodidad, se define X 1 = [ Z 1 [ 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 correspondiente.

Ejemplo

Ejemplo de ejecución (cadena de entrada no mostrada):

Propiedades

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

Gilman y Shapiro utilizaron autómatas de pila anidados para resolver el problema de la palabra en grupos virtualmente libres , de manera similar al teorema de Muller-Schupp . [ 6 ]

Notas

  1. ↑ Aho originalmente usó "$", "¢" y "#" en lugar de "[", "]" y " ] ", respectivamente. Véase Aho (1969), pág. 385 arriba.
  2. ↑ La yuxtaposición denota la concatenación de cadenas (conjuntos) y tiene una prioridad de enlace mayor 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. ↑ Aho originalmente usó el marcador de pila izquierdo y derecho, es decir, $ y ¢, como marcador de entrada derecho e izquierdo, respectivamente.
  4. ↑ El símbolo superior de una (sub)pila junto con su marcador de extremo izquierdo precedente "[" se considera un solo símbolo.

Referencias

  1. 1 2 Aho, Alfred V. (julio de 1969). "Autómatas de pila anidados" . Journal of the 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ág. 390
  4. ↑ Aho (1969), pág. 385 superior
  5. ↑ Beeri, C. (junio de 1975). "Los autómatas de pila anidados bidireccionales son equivalentes a los autómatas de pila bidireccionales" . 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 de palabras se resuelve mediante un autómata de pila anidado (Informe técnico). arXiv : math/9812028 . CiteSeerX 10.1.1.236.2029 . S2CID 12716492 .