1. Escriba expresiones regulares para denotar a cada uno de los siguientes conjuntos de palabras:
1.
Palabras con a lo sumo una pareja de 0's consecutivos y a lo sumo una pareja de 1's consecutivos.
2.
Cadenas en las que toda pareja de 0's contiguos aparece antes de cualquier pareja de 1's contiguos.
3.
Cadenas que no contienen a 101 como subcadena.
4.
Cadenas equilibradas con igual número de 0's y de 1's tales que ningún prefijo de cualquiera de ellas posee más de dos 0's que 1's ni más de dos 1's que 0's.
2. Describa en español a los lenguajes denotados por las siguientes expresiones regulares:
1.
(11+0)*(00+1)*.
2.
.
3.
.
3. Para cada una de las siguientes expresiones regulares, construya un autómata finito que reconozca al lenguaje representado por la expresión regular.
1.
10+(0+11)0*1
2.
4. Sea
el lenguaje de palabras que no contienen a la subcadena bb.
Construya un autómata finito que reconozca a L.
Encuentre una expresión regular que represente a L.
5. Demuestre las siguientes identidades para cualesquiera dos expresiones regulares E,F:
1.
(E*)*=E*
2.
3.
(E*F*)*=(E+F)*
6. Pruebe o refute a cada una de las siguientes ecuaciones:
1.
(EF+E)*E=E(FE+E)*
2.
F(EF+F)*E=EE*F(EE*F)*
3.
(E+F)*=E*+F*
7. Encuentre todas las soluciones X de la ecuación X=AX+B, donde A y B son dos expresiones regulares cualesquiera.
8. ¿Cuál de los siguientes lenguajes es regular? Justifique su respuesta:
9. Demuestre que si L es un lenguaje regular también lo es el lenguaje
Sugerencia: Si
es un autómata finito que reconoce a L considere el autómata no-determinista
tal que
10. Demuestre que si L es un lenguaje regular también lo es el lenguaje
Sugerencia: Si
es un autómata finito que reconoce a L, definamos
Consideremos un nuevo estado inicial q00. Para cada estado
consideremos la gráfica de transición Gq que coincide con
salvo en lo siguiente:
deja de considerar como finales a los estados de F,
deja de considerar como inicial a q0,
considera como final e inicial a q00,
tiende las siguientes transiciones
A partir de las gráficas Gq,
,
construya una gráfica de transición que reconozca a
.
11. Demuestre que si L es un lenguaje regular también lo es el lenguaje
consistente de los reversos de palabras en L.
12. Sea L cualquier subconjunto de 0*. Demuestre que L* es un conjunto regular.
13. Demuestre la extensión siguiente del Lema de bombeo:
Proposición 9.1
Sea L un lenguaje regular. Entonces existe un
tal que
14. Utilice el ejercicio anterior para demostrar que el lenguaje
no puede ser regular.
15. ¿Cuál es la relación de equivalencia ``'', definida según el Teorema de Myhill-Nerode, que en (0+1)* define el lenguaje
?
Concluya que L no puede ser regular.
16. Demuestre que el lenguaje
consistente de las cadenas que tiene más 0's que 1's no es regular.
17. Sea
el lenguaje de palabras que son prefijos (finitos) de la expansión decimal de :
3.1,3.14,3.141,3.1415, etc.
Demuestre que L no es regular.
18. Decida si acaso todo subconjunto de un conjunto regular es también regular.
19. Demuestre que el lenguaje formado por prefijos de palabras en un lenguaje regular es también regular.
20. Sea
y sea
.
Demuestre que todo conjunto que sea regular respecto a
también lo es respecto a
.
Muestre que el recíproco no se cumple: No todo conjunto regular respecto a
lo es respecto a
.
Siguiente:ProgramasUn nivel arriba:Expresiones regulares Anterior:Imágenes homomorfasGuillermo Morales-Luna
2000-06-27