Ejerc. 3 AFN, AFD

1.- Obtener la expresión regular que representa al lenguaje formado por todas las cadenas sobre
{a,b} que tienen un número par de b's, construir el diagrama de transición para este lenguaje.

2.- Construir el diagrama de transición para el lenguaje dado por c*(a U bc*)*
Convertir el diagrama en una tabla

3.- Sea M=(Q ,∑ ,s ,F, ς),dado por:
Q= {qo,q1,q2,q3}
∑= {0,1}
F= {qo}
s= qo

Construir el diagrama de transición

4.- La siguiente figura, es un diagrama de transición correspondiente a un AFD? Porque y por que no?

5.-Sea M un AFD ¿Cuando pertenecerá ε Є L(M)?

6.- Construir los AFD que aceptan cada uno de estos lenguajes sobre {a,b}
a) {w/ toda a de w está entre dos b's}
b) {w/w contiene la subcadena, abab}
c) {w/w no contiene ninguna de las subcadenas aa o bb
d) {/w tiene ab y ba como subcadenas}

7.- Sea M el AFN dado por Q={qo,q1}, ∑={a,b}, S=qo, F={q1} y ∆ dada en la siguiente figura
determinar si a²a y b² estan en L(M). Dibujar el diagrama de transición para M
Descargar Respuestas

Ejerc. 2 Simplificar las E.R.

1.-Simplificar

a) ( (a*b*) (b*a*)* )
b) (a*b) U (b*a)*
c) (a U b)* a (a U b)*

2.-Probar que (aa)*a=a(aa)*
3.-Simplificar las siguientesg E.R.

a) (E U aa)*
b) (E U aa) (E U aa)*
c) a (E U aa)* a U E
d) a (E U aa)* (E U aa) U a
e) (a U E) a*b
f) (E U aa)* (E U aa) a U a
g) (E U aa) (E U aa)* (E U aa)

Descargar Respuestas