Autòmat amb pila anidada

De Viquipèdia
Salta a la navegació Salta a la cerca

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.[1] 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.[2][3]

Definició formal[modifica]

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 × {ε}
  • q0Q és l'estat inicial
  • Z0 ∈ Γ és el símbol inicial de la pila
  • FQ és el conjunt d'estats finals

Configuració[modifica]

Una configuració o descripció instantània d'un autòmat amb pila anidada consisteix en el triplet ⟨ q, [a1a2...ai...an-1], [Z1X2...Xj...Xm-1] ⟩, on:

  • qQ és l'estat actual
  • [a1a2...ai...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 ≤ in es marca subratllant el símbol
  • [Z1X2...Xj...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 ≤ jm es marca subratllant el símbol.

Propietats[modifica]

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.[4]

Referències[modifica]

  1. Aho, Alfred V. «Nested Stack Automata». J. ACM, 16, 3, 1969-7, pàg. 383–406. DOI: 10.1145/321526.321529. ISSN: 0004-5411.
  2. Hall., Partee, Barbara. Mathematical methods in linguistics. Dordrecht: Kluwer Academic, 1990. ISBN 9027722447. 
  3. 1939-, Hopcroft, John E.,. Introduction to automata theory, languages, and computation. Reading, Mass.: Addison-Wesley, 1979. ISBN 020102988X. 
  4. «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.