# Autòmat amb pila anidada

En teoria d'autòmats, un autòmat amb pila anidada és un autòmat finit que pot fer ús d'una pila i crear-ne i usar-ne de noves. Com un autòmat amb pila, un amb pila anidada pot guardar dades a una pila i llegir el símbol actual, i a més, en qualsevol moment crear una nova pila, operar amb la nova i, si cal, destruir-la per seguir treballant amb la pila antiga. D'aquesta manera les piles es poden anidar de forma recursiva fins a una profunditat arbitrària. L'autòmat sempre opera amb la pila més profunda.
Un autòmat amb pila anidada pot reconèixer un llenguatge indexat i la classe de llenguatges indexats és precisament la classe de llenguatges que reconeix un autòmat amb pila anidada i determinista.

## Definició formal

Un autòmat amb pila anidada és una tupla ⟨Q,Σ,Γ,δ,q$_0$,Z$_0$,F,[,],]⟩ on:
* Q, Σ, i Γ son conjunts no buits d'estats finals, símbols d'entrada i símbol de la pila, respectivament.
* [, ], i ] son símbols especials que no estan continguts a Σ ∪ Γ:
** [ s'usa com marcador de l'esquerra per la cadena d'entrada com per la cadena a la pila
** ] s'usa com marcador de la dreta per les mateixes cadenes.
** ] s'usa com marcador de final de cadena denotant tota la pila
* Es defineix un alfabet d'entrada estès definit com a Σ' = Σ ∪ {[,]}, un alfabet de pila estès com Γ' = Γ ∪} i un conjunt de moviments com D = {-1,0,+1}
* δ, el control finit, és un mapat de Q × Σ' × (Γ' ∪ [Γ' ∪,}) cap a els subconjunts finits de Q × D × ([Γ$^*$ ∪ D) tal que:
** Q × Σ' × [Γ cap als subconjunts de Q × D × [Γ$^*$
** Q × Σ' × Γ' cap als subconjunts de Q × D × D
** Q × Σ' × [Γ' cap als subconjunts de Q × D × {+1}
** Q × Σ' ×} cap als subconjunts de Q × D × {-1}
** Q × Σ' × (Γ' ∪ [Γ') cap als subconjunts de Q × D × [Γ$^*$]
** Q × Σ' × {} cap als subconjunts de Q × D × {ε}
* q$_0$ ∈ Q és l'estat inicial
* Z$_0$ ∈ Γ és el símbol inicial de la pila
* F ⊆ Q és el conjunt d'estats finals

### Configuració

Una configuració o descripció instantània d'un autòmat amb pila anidada consisteix en el triplet ⟨ q, [a$_1$a₂...a$_i$...a$_n$$_{-1}$], [Z$_1$X₂...X$_j$...X$_m$$_{-1}$] ⟩, on:
* q ∈ Q és l'estat actual
* [a$_1$a₂...a$_i$...a$_n$$_{-1}$] és la cadena d'entrada, per conveniència es defineix que a$_0$ = [ i a$_n$ = ]. La posició actual de l'entrada a i amb 0 ≤ i ≤ n es marca subratllant el símbol
* [Z$_1$X₂...X$_j$...X$_m$$_{-1}$] és la pila, incloent-hi les subpiles. Per conveniència es defineix X$_1$ = [Z$_1$ i X$_m$ = ]. La posició actual a la pila a j amb 1 ≤ j ≤ m es marca subratllant el símbol.

## Propietats

Quan a un autòmat se'l permet re-llegir la seva entrada (autòmat de dues vies), tenir piles anidades no resulta en cap capacitat addicional per reconèixer llenguatges.

## Referències

* ↑ Aho, Alfred V. «Nested Stack Automata». J. ACM, 16, 3, 01-07-1969, pàg. 383–406. DOI: 10.1145/321526.321529. ISSN: 0004-5411.
* ↑ Hall., Partee, Barbara. Mathematical methods in linguistics. Dordrecht: Kluwer Academic, 1990. ISBN 9027722447.
* ↑ 1939-, Hopcroft, John E.,. Introduction to automata theory, languages, and computation. Reading, Mass.: Addison-Wesley, 1979. ISBN 020102988X.
* ↑ «Two-way nested stack automata are equivalent to two-way stack automata» (en anglès). Journal of Computer and System Sciences, 10, 3, 01-06-1975, pàg. 317–339. DOI: 10.1016/S0022-0000(75)80004-3. ISSN: 0022-0000.
Teoria d'autòmats: llenguatge formals i gramàtica formals :
Jerarquia de ChomskyGramàtiquesLlenguatgesMàquines abstractes
Tipus-0
Tipus-1
Tipus-2
Tipus-3
Sense restriccions
(sense nom)
Sensitiva al context
Concatenació de rang
Indexada
Sistema lineal de reescriptura lliure de context
Adjunció d'arbres
Lliure de context
Lliure de context determinista
Visibly pushdown
Regular
No recursives
Enumerable recursivament
Decidible
Sensible al context
Concatenació de rang$^*$
Indexat$^*$
Llenguatge lineal de reescriptura lliure de context
Adjunció d'arbres
Lliure de context
Lliure de context determinista
Visibly pushdown
Regular
Lliure d'estrella
Finit
Màquina de Turing
Decider
Linealment acotat
Màquina de Turing PTIME
Pila anidada
Autòmat per subprocessos
Autòmat amb pila d'arbre restringit
Pila incrustada
Autòmat amb pila no-determinista
Autòmat amb pila determinista
Visibly pushdown
Finit
Sense comptadors(amb monoides finits aperiòdics)
Finit acíclic :
Cada categoria de llenguatges, excepte aquells marcats per $^*$, és un subconjunt de la categoria superior. Qualsevol llenguatge en aquesta categoria es genera per una gramàtica i per un autòmat de la categoria de la mateixa línia. :