7/29/2019 Ejercicios Del Capitulo 2 (Autoguardado)

1/3

Ejercicios del Cpitulo 2

2.1 Obtener una expresin regular para cada uno de los siguientes casos:

a)El lenguaje formado por todas las cadenas de unos y ceros queinician con dos ceros consecutivos.

b)El lenguaje formado por todas las cadenas de unos y ceros quetenga un nmero de ceros divisible entre tres.

c) El lenguaje formado por todas las cadenas de unos y ceros quetienen al menos dos unos consecutivos.

d)El lenguaje formado por todas las cadenas de unos y ceros que notengan mas de tres ceros.

e) El lenguaje formado por todas las cadenas de unos y ceros quesolamente tenga una ocurrencia de tres ceros consecutivos.

f) El lenguaje formado por todas las cadenas de dgitos querepresenten un nmero entero positivo(base 10) correctamente

escrito.

g) El lenguaje formado por todas las cadenas de unos y ceros quetengan longitud menor o igual a 5h)El lenguaje formado por todas las cadenas de unos y ceros que no

finalicen en 01.

i) El lenguaje formado por todas las cadenas de unos y ceros queterminen en 1 y no contengan a la subcadena 00.

j)

El lenguaje formado por todas las cadenas de unos y ceros cuyalongitud es mltiplo de 5.

k)El lenguaje formado por todas las cadenas de unos y ceros queinicien o terminen en 00 o en 11.

7/29/2019 Ejercicios Del Capitulo 2 (Autoguardado)

2/3

2.2 Dada la expresin regular (ab)+(cb)*. Indicar si las siguientes

cadenas pertenecen o no al lenguaje que representa.

a) w1=abcb Si perteneceb)w2= No pertenecec) w3=cbcbb No perteneced)w4=ab no pertenecee) w5=abcbcb Si pertenece

2.3 Determinar las cadenas que pertenecen al lenguaje descrito por la

expresin regular siguiente: c*a (bc)* b* .

L= {a, ca, cca, ccca.,, bc, bcbc , b, bb, bbb}

a).- a,ca, , bc,b

b).- a,caca, ,bcbc,bb

2.4 Dada la expresin regular a ( b c ) a ( a b c ) * a, Cuntas

cadenas de longitud 6 representa?

17 cadenas

2.5 Simplificar las siguientes expresiones:

a) ( ab)* = {,ab,abab,ababab,abababab.}b)a ( aa)* a = {aa,aaaa,aaaaaa,aaaaaaaa..}c) (a ) a*b = {ab,aab,aab.}

7/29/2019 Ejercicios Del Capitulo 2 (Autoguardado)

3/3

d)(((a*a)b) b) = {a,aa,aa,aaa,aaa,ab,aab,aaab,b}e) ( aa) (( aa)* ={,a,aa,aa,aaa,aaa}f)

(aa)

*

a

(aa)*

= {aa,aaaa,aaaaaa..}g) (a b)* a (a b)*= {a,aa,aa,aaa,aaa,ba,bba,bbba.}h)a( aa)* ( aa) a = {aaa,aaaaa,aaaaaaa,aaaaaaaaa}

2.6 Simplificar las siguientes expresiones:

a) * a* b* (a* b*)+

b) (( a*b*)*. (b*a*)* )*

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

d) ( a+) bb+ ( c)*

e) y (

x+

)

(yy+

(

x)*

)f) ( x) ( x)+ ( x)*

g) (a b) ( aa)* ( aa)(ab)

h) a*b ((ab) a*b)* a*b