Lenguajes libres de contexto

INSTITUTO TECNOLOGICO DE VERACRUZ

PROGRAMA EDUCATIVO
ING.SISTEMAS COMPUTACIONALES

EXPERIENCIA EDUCATIVA
Teoría de la Computación

DOCENTE
M.S.I PATRICIA HORTA ROSADO

TRABAJO
Lenguajes Libres de Contexto

ESTUDIANTE
CAMACHO OJEDA ANJEL ENRIQUE

11 DE NOVIEMBRE 2011

Lenguajes libres de contexto.

Autómata de pila:
Los autómatas de pila, en forma similar a como se usan losautómatas finitos, también se pueden utilizar para aceptar cadenas de un lenguaje definido sobre un alfabeto A.
Los autómatas de pila pueden aceptar lenguajes que no pueden aceptar los autómatas finitos.
Un autómata de pila cuenta con una cinta de entrada y un mecanismo de control que puede encontrarse en uno de entre un número finito de estados. Uno de estos estados se designa como estadoinicial, y además algunos estados se llaman de aceptación o finales. A diferencia de los autómatas finitos, los autómatas de pila cuentan con una memoria auxiliar llamada pila. Los símbolos (llamados símbolos de pila) pueden ser insertados o extraídos de la pila, de acuerdo con el manejo last-in-first-out (LIFO).
Las transiciones entre los estados que ejecutan los autómatas de pila dependen de lossímbolos de entrada y de los símbolos de la pila. El autómata acepta una cadena x si la secuencia de transiciones, comenzando en estado inicial y con pila vacía, conduce a un estado final, después de leer toda la cadena x.

Autómata de pila reconocedor determinístico
APD=<E, A , P, δ, e0, Z0, F>
E: Conjunto finito de estados,
A: Alfabeto o conjunto finito de símbolos de la cinta deentrada,
P: Alfabeto o conjunto finito de símbolos de la Pila. P∩A= ∅
δ: función de transición de estados
e0: Estado inicial e0 ∈ E.
Z0: Símbolo distinguido Z0 ∈ P
F: Conjunto de estados finales o estados de aceptación. F ⊆ E.

La función de transición definida como: δ:E x ( A ∪{ε}) x P → E x P∗
1) δ( ei , a, X) =( ej , α)
2) δ( ei , ε, X) =( ej , α) donde a ∈ A; X ∈ P; α ∈ P∗ ; ei , ej ∈E.

Nota: Si existe transición de tipo (2), sólo se garantiza que AP es determinístico si
∀ s ∈ A, δ( ei , s, X) está indefinida.

Descripción instantánea
Una configuración de un AP es una tripla <e ,σ ,π> donde e: estado_actual; σ: cadena de entrada a
ser leída; π: contenido de la pila.
Luego, se define una relación de transición |- en el espacio de posibles configuraciones del AP,tanto si:

(1)
< ei , aω,Xβ > |- < ej , ω, αβ > Si existe la transición tipo (1), el AP pasa al estado
ej, avanza la cabeza lectora y reemplaza el tope X
por α.

(2)
< ei , aω, Xβ > | < ej , aω, αβ > Si existe la transición tipo (2), el AP pasa al estado
ej, NO avanza la cabeza lectora y reemplaza el tope
X por α.

donde a∈A; ω∈A∗; X∈P; α,β ∈P∗; ei ,ej ∈ ELa función de transición de estados de un AP puede ser representada por un diagrama donde los
nodos representan los estados y los arcos transiciones. Si existe transición tipo (1), el arco queda
rotulado de la siguiente manera:

Si el estado actual es ei y la cabeza lectora apunta un símbolo a, y el tope de la pila es X, entonces
cambiar al nuevo estado ej, avanzar la cabeza lectora, ysustituir el símbolo del tope X en la pila por
la cadena α
Por ejemplo:

Si αZYX deja X , apila Y, y apila Z (nuevo tope Z). donde X, Y, Z ∈P
Si αXX deja X y apila X (nuevo tope X).
Si αX deja X como el mismo tope (no altera la pila)
Si αelimina X, y el nuevo tope es el símbolo por debajo (desapila)

Ejemplo 1
A={a,b,c}
L1={ ωcωR / ω{a,b}∗}
APD1 es un autómata de pilaque reconoce L1.
APD1=<{e0,e1,e2},{a,b,c},{X,Y, Z0}, e0, Z0, {e2}>

Arboles de derivación

== Arboles De Derivación ==
Existen básicamente dos formas de describir cómo en una cierta gramática una cadena puede ser derivada desde el símbolo inicial. La forma más simple es listar las cadenas de símbolos consecutivas, comenzando por el símbolo inicial y finalizando con la cadena y las...