Autòmat amb pila

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

Lògica combinacionalAutòmat finitAutòmat amb pilaMàquina de TuringTeoria d'autòmatsAutomata theory.svg
Quant a la imatge
Classes d'autòmates
(En fer clic a cada capa, apareix un article sobre aquest tema )

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ó formalModifica

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ènciesModifica

  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.