Trbaajos

TAREA 4

Capitulo 3 - 4

TEORIA DE AUTOMATAS Y LENGUAJES FORMALES (CC-931)

Académico:  Jacqueline Manriquez

Ayudante: Evelyn Rojas

I semestre 2014

1. Para el AFD siguiente, con Σ ={0,1} y F={q2}

1. Determinar el AFD del complemento respecto al alfabeto {0, 1, 2}.
2. Determine el AFD del complemento respecto al alfabeto {1}. Describa la expresión regular de este AFD.
3. ¿Qué ocurre si estudia el complemento del AFD respecto al alfabeto 0?

1. Describa los AFD que aceptan las expresiones regulares sobre el alfabeto binario Σ={0, 1} , r1=0(01)*1 y r2=(01)*(ε+1). Para ellos determinar:

1. Σ* - L(r1) (el complemento del lenguaje de r1)
2. Σ* - L(r2) (el complemento del lenguaje de r2)
3. La unión de los complementos de ambos lenguajes.
4. L(r1) ∩ L(r2) (la intersección de ambos lenguajes) ¿Qué strings están en la intersección?

1. Sea el homomorfismo h:{0, 1} → {a, b, c}* definido por: h(0)=ab y h(1)=bc. Determinar:

1. h[(01 + 10)*]
2. h-1[(a + bc)*] (describir el AFD correspondiente y su expresión regular)

1. Sea el AFN sobre ∑={0, 1} y con estados finales F={q1,q4}. Minimice el numero de estados, describiendo la tabla de estados distinguibles e indicando los estados equivalentes. Grafique el AFD equivalente indicando las clases de equivalencias que forman los estados.

1. Suponga que h es el homomorfismo que transforma el alfabeto {0,1,2} en el alfabeto {a,b}. definamos como: h(0)=a; h(1)=ab y h(2)=ba

1. ¿Qué es h(0120)?
2. Si el lenguaje es L(01*2), ¿Qué es h(L)?

1. Sea L=[(0+1)(0+1)]*(0+1)1. Determine el AFD de L, e identifique los cuocientes L/P y L/R en que P=0(10)* y R=(01)+.
2. Probar que L={0m1n | n + m > 2n -m}, para n positivo, no es un conjunto regular usando el Lema de Bombeo.

...