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,Σ,Γ,δ,q0,Z0,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 × {ε} q0 ∈ Q és l'estat inicial Z0 ∈ Γ é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, [a1a₂...ai...an-1], [Z1X₂...Xj...Xm-1] ⟩, on:
q ∈ Q és l'estat actual [a1a₂...i...an-1] és la cadena d'entrada, per conveniència es defineix que a0 = [ i an = ]. La posició actual de l'entrada a i amb 0 ≤ i ≤ n es marca subratllant el símbol [Z1X₂...j...Xm-1] és la pila, incloent-hi les subpiles. Per conveniència es defineix X1 = [Z1 i Xm = ]. 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
Categoria:Llenguatges formals Categoria:Complexitat computacional