• Author / Uploaded
• Eduar Velasquez

Citation preview

Universidad Mariano Gálvez Facultad de Ingeniería Sistemas de Información Autómatas y Lenguajes Formales Ing. Jose Félix

Laboratorio No. 1 I Serie. Realice el conjunto para las siguientes expresiones regulares. 1. (a|b|c)(a|b|c) 2. a(a|b)* 3. a(aa|b)* 4. 1(11+00)* 5. 11(11+00)|(00)* 6. De las 3 expresiones regulares, cuales son equivalentes al mismo conjunto: a. (a+b)* b. a*b* c. (a*b*)* II Serie. Dado los siguientes lenguajes definidos sobre el alfabeto Σ={0, 1}, encontrar las expresiones regulares que lo denotan. 1. 2. 3. 4. 5. 6.

Cadenas que tienen un número impar de 1’s Cadenas que tienen un numero par de 0’s Cadenas con solo un 0 Cadenas binarias que no tienen dos 1’s consecutivos o es cadena vacía. Cadenas binarias que empiezan y terminan con 0 Cadenas impares en donde contenga un 1 en medio de la cadena

III. Serie Dada la siguiente definición formal de un AFN, construya la máquina de estados por medio de un diagrama que la represente. 1.

¿Cuál sería la expresión regular para esta máquina de estados? De las siguientes cadenas mencione cuales son aceptadas por la AFN construido: 2. 3. -

bba ab abb aaaba bbbaa a b De forma improvisada construya un AFN por medio de esta expresión regular: ab(a+b)*ab Utilizando las reglas de construcción para los AFN, construya los AFN para las siguientes expresiones regulares y represéntelos por medio de la definición formal. (a+b)*b*b (a+b)ab (a+b)(a+b) ((a+b)+(a+b))ab (a+b)+(a+b)*ab