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₀,Z₀,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₀ ∈ Q és l'estat inicial
• Z₀ ∈ Γ é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₁a₂...a_i...a_n-1], [Z₁X₂...X_j...X_m-1] ⟩, on:

• q ∈ Q és l'estat actual
• [a₁a₂...a_i...a_n-1] és la cadena d'entrada, per conveniència es defineix que a₀ = [ i a_n = ]. La posició actual de l'entrada a i amb 0 ≤ i ≤ n es marca subratllant el símbol
• [Z₁X₂...X_j...X_m-1] és la pila, incloent-hi les subpiles. Per conveniència es defineix X₁ = [Z₁ 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.