Siguiente: Máquinas de Turing Un nivel arriba: Autómatas Anterior: Autómatas lineales

Autómatas de pila no-deterministas

Los autómatas de pila no-deterministas coinciden con sus homólogos de pila salvo en que su transición no es propiamente una función. Aquí se tiene que la transición es un subconjunto $t \subset (Q \times T \times V) \times (Q \times V^*)$.


Ejemplo: El lenguaje de palíndromas sin marca central

$$L = \{ \mbox{\bf x} \in (0 + 1)^* \vert \mbox{\bf x} = \mbox{\rm reverso}(\mbox{\bf x}) \}$$

es reconocido por un autómatas de pila no-determinista que funciona de acuerdo con el sigiente procedimiento:

Avanzando a la derecha, se almacena primeramente cada símbolo y cuando se ``cree'' estar a la mitad, se compara cada símbolo leído con el tope de la pila. Si coinciden, se continúa. En otro caso se marca un error.

El no-determinismo del autómata está en que no se precisa en qué momento pasará al estado de desempilar. Transita a ése de manera indeterminada.