aut

INDICE

TEMA 7.-AUTOMATAS CON PILA

DEFINICIONES PREVIAS

LENGUAJE ACEPTADO POR UN AUTOMATA CON PILA

AUTOMATAS CON PILA Y LENGUAJES LIBRES DEL CONTEXTO

DEFINICIONES PREVIAS

Los lenguajes generados por las gramáticas libres de contexto también tienen un autómata asociado que es capaz de reconocerlos, son parecidos a los autómatas finitos deterministicos, solo que ahora tendrán un dispositivo de memoria de capacidad ilimitada: una pila.

Los autómatas con pila no deterministicos (APND) y deterministicos (APD) no aceptan las mismas familias de lenguajes.
Los APND son los asociados con los lenguajes libres de contexto o de tipo 3.
Los APD aceptan una familia mas restringida de lenguajes.

DEFINICION
Un autómata con pila no deterministico es una séxtupla (Q,A,B,d ,q₀,Z,F) en la que

		Q	es un conjunto finito de estados.
		A	es un alfabeto de entrada.
		B	es un alfabeto para la pila.
		d	es la función de transición d:Qx(A∪ {ε })xB→Ã (QxB)
		q₀	es el estado inicial.
		Z	es el símbolo inicial de la pila.
		F	es el conjunto de estados finales.

La función de transición aplica cada estado, cada símbolo de entrada (incluyendo la e ) y cada símbolo tope de la pila en un conjunto de posibles movimientos. Cada movimiento consiste de un estado en el que encuentra el autómata y una cadena por la que se reemplaza el tope de la pila.

EJEMPLOS.-

1.-Sea el autómata M=({q₁,q₂},{0,1,c},R,B,G},d ,q₁,R,∅ ) donde

		d (q₁,0,R)={(q₁,BR)}	d (q₁,1,R)={(q₁,GR)}
		d (q₁,0,B)={(q₁,BB)}	d (q₁,1,R)={(q₁,GB)}
		d (q₁,0,G)={(q₁,BG)}	d (q₁,1,R)={(q₁,GG)}
		d (q₁,c,R)={(q₂,R)}	d (q₁,c,R)={(q₂,B)}
		d (q₁,c,G)={(q₂,G)}	d (q₂,0,R)={(q₂,ε )}
		d (q₂,1,G)={(q₂,ε )}	d (q₂,ε ,R)={(q₂,ε )}

La forma de interpretarlo es que:

Se llama descripción instantánea o configuración de un autómata con pila a una tripleta (q,u,a )∈ QxA*xB* en el que q es el estado en el que se encuentra el autómata, u es la parte de la cadena de entrada que queda por leer y a el contenido de la pila (el primer símbolo es el tope de la pila).

DEFINICION

Se dice que de la configuración (q,au,Za ) se puede llegar a la configuración (p,u,ba ) y se escribe (q,au,Za )Ø (p,u,b a ) si y solo si (p,b )∈ d (q,a,Z) donde a puede ser cualquier símbolo de entrada a la ε .

DEFINICION

Si C₁ y C₂ son dos configuraciones, se dice que se puede llegar de C₁a C₂ mediante una sucesión de pasos de calculo y se escribe C₁ØC2 si y solo si existe una sucesión de configuraciones T1,..,Tn tal que C1=T1ØT2Ø_...Ø T_n=C₂.

DEFINICION

Si M es un APND y u∈ A* se llama configuración inicial corresponde a esta entrada a (q₀,u,Z₀) donde q₀es el estado inicial y Z₀el símbolo inicial de la pila.

EJEMPLO.- Teniendo en cuenta el autómata de pila del Ejemplo 1. cual es la configuración inicial

LENGUAJE ACEPTADO POR UN AUTOMATA CON PILA

Existen dos criterios para determinar el lenguaje aceptado por un APND:

			a) Lenguaje aceptado por estados finales
				L(M)={w∈A* / (q₀,w,Z₀)Ø *(p,ε ,g ) p∈ F}
				Una palabra es aceptada, si se puede llegar a un estado final después de consumir la entrada.
			b) Lenguaje aceptado por pila vacía
				N(M)={w∈A* / (q₀,w,Z₀)Ø *(p,ε ,ε ) p∈ Q}

Los estados finales no tienen ningún significado, y una palabra se acepta si cuando se termina de leer la entrada la pila se queda vacía.

EJEMPLO.- Según el Ejemplo2. La palabra 011c110 es aceptada por el autómata por el criterio de pila vacía (011c110∈ N(M)).

TEOREMA:

a)Si M es un APND entonces existe otro autómata M' tal que N(M)=L(M').

b)Si M₁ es un APND entonces existe otro autómata M₁^' tal que L(M₁)=N(M').

DEFINICION:

Un autómata con pila se dice que es deterministico(APD) si y solo si se verifican las dos condiciones siguientes:

			1)" q∈ Q y Z∈ B, si d (q,ε ,Z)¹f entonces d (q,a,Z)=f" a∈ A.
			2)" a∈ AÈ {ε }, z∈ B, q∈ F, d (q,a,Z) nunca contiene mas de un elemento.

El ejemplo con el que venimos trabajando es un autómata con pila deterministico.

AUTOMATAS CON PILA Y LENGUAJES LIBRES DEL CONTEXTO

TEOREMA.-

Si un lenguaje es generado por una gramática libre de contexto, entonces es aceptado por un APND, es decir, los APND aceptan los mismos lenguajes que los generados por las gramáticas de tipo 2.

EJEMPLO.- Para la gramática en forma normal de Greibach:

		S → aAA
		a → aS \| bS \| a

¿cuál es el autómata ?
TEOREMA.-

Si L=N(M) donde M es un APND, existe una gramática libre del contexto G tal que L(G)=L.

EJEMPLO.-
Si partimos del autómata M=({q₀,q₁},{0,1},{X,Z₀},d ,q₀,Z₀,f ) donde

		d (q₀,0,Z₀)={(q₀,XZ₀)}	d (q₁,1,X)={(q₁,ε )}
		d (q₀,0,X)={(q₀,XX)}	d (q₁,ε ,X)={(q₁,ε )}
		d (q₀,1,X)={(q₀,e )}	d (q₁,e ,Z₀)={(q₁,ε )}

las producciones de la gramática asociada eliminando símbolos y producciones inútiles son