Lenguajes y Autómatas I
RESPUESTA DE LA TAREA 4
1. Obtener una expresión regular para cada uno de los siguientes lenguaje sobre el alfabeto = { 0, 1 }:
a) El lenguaje formado por todas las cadenas que inician con dos ceros consecutivos. 00 ( 1 0 )*
b) El lenguaje formado por todas las cadenas que tienen al menos dos unos consecutivos. ( 1 0 )* 11 ( 1 0 )*
c) El lenguaje formado por todas las cadenas que contienen exactamente tres ceros. 1*01*01*01*
d) El lenguaje formado por todas las cadenas que terminan en cero y contienen exactamente dos ceros. 1*01*0
e) El lenguaje formado por todas las cadenas que inician y terminan en cero. 0 ( 1 0 )* 0
f) El lenguaje formado por todas las cadenas que contienen una cantidad par de ceros. 1*( 01*01*)*
g) El lenguaje formado por todas las cadenas que terminan en uno y contienen exactamente dos ceros. 1*01*01+
h) El lenguaje formado por todas las cadenas que contienen una cantidad impar de ceros. 1*0(1*01*0)*1*
i) El lenguaje formado por todas las cadenas que inician con uno y contienen cuando mucho dos ceros. 1+ 1+01* 1+01*01*
j) El lenguaje formado por todas las cadenas que tenga un número de ceros divisible entre tres. 1*( 01*01*01* )*
k) El lenguaje formado por todas las cadenas que tengan una sola ocurrencia de tres ceros consecutivos. 1*(01+ 001+)* 000 (1+0 1+00)*1*
l) El lenguaje formado por todas las cadenas que tengan longitud igual a 4. ( 0 1 )4
m) El lenguaje formado por todas las cadenas que tengan longitud menor o igual a 6. ( 1 0 )6
n) El lenguaje formado por todas las cadenas que tengan longitud mayor o igual a 3. (1 0 )3(1 0 )*
o) El lenguaje formado por todas las cadenas cuya longitud es múltiplo de 5. (( 0 1 ) 5)*
p) El lenguaje formado por todas las cadenas que no finalicen en 01. ( 0 1 )* ( 11 0 ) 1
q) El lenguaje formado por todas las cadenas que terminen en uno y no contengan a la subcadena 00. ( 01 1 )+
r) El lenguaje formado por todas las cadenas que inicien o terminen en 00 o en 11. (11 00)(1 0)* (1 0)*(11 00)
2. Describa con palabras el significado de cada una de las siguientes expresiones regulares:
a) (00)* Las cadenas formadas por una cantidad par de ceros, (incluyendo la cadena vacía).
b) 0*1* Las cadenas que inician con cualquier cantidad de ceros seguida por cualquier cantidad de unos.
c) 1(0 1)* Las cadenas de ceros y unos que inician con uno.
d) (0 1)*00 Las cadenas de ceros y unos que terminan con doble cero.
e) (0 1)*10(0 1)* Las cadenas de ceros y unos que contienen la subcadena 10.
f) 1*01*0(0 1)* Las cadenas de ceros y unos que contienen al menos dos ceros.
Lenguajes y Autómatas I
3. Dada la expresión regular (ab)+ (cb)*. Indicar si las siguientes cadenas pertenecen o no al lenguaje que representa:
a) w1 = abcb No
b) w2 = Si
c) w3 = cbcbb No
d) w4 = ab Si
e) w5 = abcbcbcb No
4. Determinar las cadenas que pertenecen al lenguaje descrito por la expresión regular: c*a (bc)* b*.
L = { a, ca, cca, ccca, …, , bc, bcbc, bcbcbc, …, b, bb, bbb, bbbb, … }
5. Dada la expresión regular a ( b c ) a ( a b c )* a, ¿Cuántas cadenas de longitud 6 representa? El paréntesis (b c ) representa 2 opciones
y el paréntesis ( a b c )* se debe reemplazar por ( a b c )2 para que se cumpla que las cadenas sean de longitud 6, y representa 9 diferentes
combinaciones de símbolos, por lo tanto la respuesta es 18.
