En la teoría de los autómatas , un autómata de pila anidado es un autómata finito que puede hacer uso de una pila que contiene datos que pueden ser pilas adicionales. [1] Como un autómata de pila , un autómata de pila anidado puede subir o bajar en la pila y leer el símbolo actual; además, en cualquier lugar puede crear una nueva pila, operar en esa, eventualmente destruirla y continuar operando en la pila vieja. De esta forma, las pilas se pueden anidar de forma recursiva hasta 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 pushdown integrados , que tienen menos poder de cálculo. [ cita requerida ]
Definicion formal
Autómata
A (no determinista de dos vías) anidada pila autómata es una tupla ⟨ Q , Σ, Γ, δ, q 0 , Z 0 , F , [,], ] ⟩ donde
- Q , Σ y Γ es 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 figuran en Σ ∪ Γ,
- [se usa como marcador de extremo 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 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 un mapeo de Q × Σ '× (Γ' ∪ [Γ '∪ { ] , [ ] }) en subconjuntos finitos de Q × D × ([Γ * ∪ D ), tal que δ mapea [nota 2]
Q × Σ '× [Γ | en subconjuntos de Q × D × [Γ * | (modo pushdown), | |
Q × Σ '× Γ' | en subconjuntos de Q × D × D | (modo de lectura), | |
Q × Σ '× [Γ' | en subconjuntos de Q × D × {+1} | (modo de lectura), | |
Q × Σ '× { ] } | en subconjuntos de Q × D × {-1} | (modo de lectura), | |
Q × Σ '× (Γ' ∪ [Γ ') | en subconjuntos de Q × D × [Γ * ] | (modo de creación de pila), y | |
Q × Σ '× {[ ] } | en subconjuntos de Q × D × { ε }, | (modo de destrucción de pila), |
- De manera informal, el símbolo superior de una (sub) pila junto con su marcador de extremo izquierdo anterior "[" se ve como un solo símbolo; [4] luego δ 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 se mueve en la entrada, y
- la dirección en la que se mueve en la pila, o la cadena de símbolos para reemplazar el símbolo de la pila superior.
- 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 un autómata de este tipo consiste en un triple ⟨ q , [ un 1 a 2 ... un i ... un 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; por conveniencia, se define un 0 = [y un n =] [nota 3] La posición actual en la entrada, a saber. i con 0 ≤ i ≤ n , se marca subrayando el símbolo respectivo.
- [ Z 1 X 2 ... X j ... X m -1 ] es la pila, incluidas las subestaciones; por conveniencia, se define X 1 = [ Z 1 [nota 4] y X m = ] . La posición actual en la pila, a saber. j con 1 ≤ j ≤ m , se marca subrayando el símbolo respectivo.
Ejemplo
Un ejemplo de ejecución (cadena de entrada no mostrada):
Acción | Paso | Apilar | |||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
1: | [ un | B | [ k | ] | [ p | ] | C | ] | |||||
crear sub-pila | 2: | [ un | B | [ k | ] | [ p | [ r | s | ] | ] | C | ] | |
música pop | 3: | [ un | B | [ k | ] | [ p | [ s | ] | ] | C | ] | ||
música pop | 4: | [ un | B | [ k | ] | [ p | [] | ] | C | ] | |||
destruir sub-pila | 5: | [ un | B | [ k | ] | [ p | ] | C | ] | ||||
mover hacia abajo | 6: | [ un | B | [ k | ] | [ p | ] | C | ] | ||||
ascender | 7: | [ un | B | [ k | ] | [ p | ] | C | ] | ||||
ascender | 8: | [ un | B | [ k | ] | [ p | ] | C | ] | ||||
empujar | 9: | [ un | B | [ k | ] | [ n | o | pag | ] | C | ] |
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 idioma adicionales, en comparación con las pilas simples. [5]
Gilman y Shapiro usaron autómatas de pila anidados para resolver el problema verbal en ciertos grupos . [6]
Notas
- ^ Aho originalmente usó "$", "¢" y "#" en lugar de "[", "]" y " ] ", respectivamente. Ver Aho (1969), p. 385 arriba.
- ^ Juxataposition denota 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 Γ'.
- ^ Aho originalmente usó el marcador de pila izquierdo y derecho, a saber. $ y ¢, como marcador de entrada derecho e izquierdo, respectivamente.
- ^ El símbolo superior de una (sub) pila junto con su marcador final izquierdo anterior "[" se ve como un solo símbolo.
Referencias
- ↑ a b 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 .
- ^ Partee, Barbara ; Alice ter Meulen; Robert E. Wall (1990). Métodos matemáticos en lingüística . Editores académicos de Kluwer. págs. 536 –542. ISBN 978-90-277-2245-4.
- ^ John E. Hopcroft, Jeffrey D. Ullman (1979). Introducción a la teoría, los lenguajes y la computación de los autómatas . Addison-Wesley. ISBN 0-201-02988-X. Aquí: p.390
- ↑ Aho (1969), p. 385 arriba
- ^ 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". Revista de Ciencias de la Computación y Sistemas . 10 (3): 317–339. doi : 10.1016 / s0022-0000 (75) 80004-3 .
- ^ Shapiro, Robert Gilman Michael (4 de diciembre de 1998). En grupos cuyo problema verbal se resuelve mediante un autómata de pila anidado (Informe técnico). arXiv : matemáticas / 9812028 . CiteSeerX 10.1.1.236.2029 . S2CID 12716492 .