Autòmat amb pila

De Viquipèdia
Salta a la navegació Salta a la cerca
Classes d'autòmats

Un autòmat amb pila és un tipus d'autòmat que utilitza una pila.

Aquests autòmats s'utilitzen en teoria de la computabilitat i són més potents que un autòmat finit però menys capaços que una Màquina de Turing.[1] Si en tot moment només és possible una i només una transició, llavors l'autòmat és un autòmat amb pila determinista. En altre cas, és diu que l'autòmat és un autòmat amb pila general o no determinista.

Els llenguatges que reconeixen els autòmats amb pila pertanyen al grup dels llenguatges lliures del context en la Jerarquia de Chomsky.[2]

Definició formal[modifica]

Formalment, un autòmat amb pila es pot descriure com una sèptupla on:

  • és un conjunt finit d'estats.
  • i són alfabets (símbols d'entrada i de la pila respectivament)
  • és l'estat inicial
  • és el símbol inicial de la pila
  • és un conjunt d'estats d'acceptació o finals

La interpretació de , amb , y és la següent:

Quan l'estat de l'autòmat és , el símbol que el cap lector està inspeccionant en aquell moment es , i a dalt de la pila trobem el símbol , es fan les següents accions:

  • Si , és a dir, no és la cadena buida, el cap lector avança una posició per inspeccionar el següent símbol
  • S'elimina el símbol de la pila de l'autòmat
  • Es seleccionen un parell d'entre els existents en la definició de , la funció de transició del autòmat
  • S'apila la cadena , amb a la pila del autòmat, quedant el símbol a dalt de la pila
  • Es canvia el control de l'autòmat a l'estat

Referències[modifica]

  1. Hopcroft, J.E.; Ullman, J.D. «Nonerasing stack automata». Journal of Computer and System Sciences, 1, 2, pàg. 166–186. DOI: 10.1016/s0022-0000(67)80013-8.
  2. 1939-, Hopcroft, John E.,. Introduction to automata theory, languages, and computation. Reading, Mass.: Addison-Wesley, 1979. ISBN 020102988X.