Asd-Esto Sdaqwecvxc

PONTIFICIA UNIVERSIDAD CATÓLICA DEL ECUADOR
FACULTAD DE INGENIERÍA
ESCUELA DE SISTEMAS
NOMBRE: Franklin Lozada C.
NIVEL: 4
FECHA: 2011-09-20
1. Σ = {x,y,z}
Hacer el autómata finitodeterminista del lenguaje:
L = { ω| ω tiene: (un número impar de x´s O un número par de y´s) Y un número impar de z´s

2. Muestre que si L es un LR, también es regular el lenguaje de las cadenas de L escritasa la inversa. (Tip: Con base en el autómata de L , dar un procedimiento GENERAL para construír el  autómata de las inversas de L) 
Cada transición de salida de un estado será la transición dellegada a ese estado manteniendo el símbolo.
Ejemplo: Si del estado AC1 con una transición de x llegamos al estado BC1, su inversa sería del estado BC1 con una transición de x llegamos al estado AC1; demodo que las transiciones de salida de cada estado serán las de llegada a este.
El autómata para que cumpla con sus cadenas inversas seguirá siendo el mismo.
Si tenemos la cadena XXXYYZ que si cumplecon el lenguaje, su inversa sería ZYYXXX, la cual también cumple.

3. Haga la expresión regular del lenguaje del alfabeto {x,y,z} de las cadenas que no contienen mas de dos x´s consecutivas.

ER= (y,z)* x (y,z)* x (y,z)*
4. Utilizando el lema de bombeo demuestre que el lenguaje del alfabeto Σ = {x} cuyas cadenas tienen como longitud un número cuadrado perfecto NO ES UN LENGUAJE REGULAR.
xpertenece al lenguaje
xxxx pertenece al lenguaje
xxxxxxxxx pertenece al lenguaje
Tenemos según el lema de bombeo:
X=x
Y=x*
Z=x
Por lo que tenemos x x* x, esta expresión no cumple con todos loscasos, entonces no es un lenguaje regular.
5. Encuentre la expresión regular simple que represente la intersección de los siguientes lenguajes:
a) (x,y*) intersección (x,y)*
x,y*
b) (x · (x,y)*)intersección ((x,y)* · y)
x (x,y)* y
c) (((x,y) · y) (x,y)*) intersección (y · (x,y)* )
yy(x,y)*
d) ((x,y)(x, Ф )) intersección ((x,y)(x · y)*)
x,y
6. Σ = {0,1}
Hacer el autómata finito  del...