Siguiente: Programas Un nivel arriba: Expresiones regulares Anterior: Imágenes homomorfas

Ejercicios

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.

$(1+01+001)^*(\mbox{\it nil\/}+0+00)$.

3.

$\left(00+11+(01+10)(11+00)^*(01+10)\right)^*$.

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.

$01\left(\left((10)^*+111\right)^*+0\right)^*1$

4. Sea $L\subset(a+b)^*$ 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.

$(\mbox{\it nil\/}+E)^*=E^*$

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:

$$\begin{eqnarray*}L_1 &=& \{0^{2n}\vert n\geq 0\} \\ L_2 &=& \{\sigma\in(0+1)^*... ... &=& \{\sigma\in(0+1)^*\vert00\mbox{\rm no parece en }\sigma\} \end{eqnarray*}$$

9. Demuestre que si L es un lenguaje regular también lo es el lenguaje

$$\mbox{\it Saltear\/}(L)=\{e_1e_3\cdots e_{2i-1}\cdots e_{2n-1}\vert e_1e_2\cdots e_{2n-1}e_{2n}\in L\}.$$

Sugerencia: Si $\mbox{\it AF\/}=(Q,\mbox{\it Ent\/},\mbox{\it tran\/},q_0,F)$ es un autómata finito que reconoce a L considere el autómata no-determinista $\mbox{\it AND\/}=(Q,\mbox{\it Ent\/},\mbox{\it tran\/}',q_0,F)$ tal que

$$\forall p,q\in Q, e\in\mbox{\it Ent\/}:\ \ (p,e,q)\in\mbox{\i... ...row\; \exists f\in\mbox{\it Ent\/}:\mbox{\it tran\/}^*(p,ef)=q.$$

10. Demuestre que si L es un lenguaje regular también lo es el lenguaje

$$\mbox{\it Ciclo\/}(L)=\{\sigma_2\sigma_1\vert\sigma_1\sigma_2\in L\}.$$

Sugerencia: Si $\mbox{\it AF\/}=(Q,\mbox{\it Ent\/},\mbox{\it tran\/},q_0,F)$ es un autómata finito que reconoce a L, definamos

$$\begin{eqnarray*}S^{-1}(F) &=& \{q\in Q\vert\exists \sigma:\mbox{\it tran\/}^*(q... ...,\sigma)=q\} \ :\mbox{\rm estados accesibles desde el inicial.} \end{eqnarray*}$$

Consideremos un nuevo estado inicial q₀₀. Para cada estado $q\in S(q_0)\cap S^{-1}(F)$ consideremos la gráfica de transición G_q que coincide con $\mbox{\it AF\/}$ salvo en lo siguiente:

• deja de considerar como finales a los estados de F,
• deja de considerar como inicial a q₀,
• considera como final e inicial a q₀₀,
• tiende las siguientes transiciones $\mbox{\it nil\/}$
  
  $$\begin{eqnarray*}q_{00} &\stackrel{\mbox{\it nil\/}}{\mapsto}& q \\ q &\stackr... ...orall q_f\in F: q_f &\stackrel{\mbox{\it nil\/}}{\mapsto}& q_0 \end{eqnarray*}$$
  
  

A partir de las gráficas G_q, $q\in S(q_0)\cap S^{-1}(F)$, construya una gráfica de transición que reconozca a $\mbox{\it Ciclo\/}(L)$.

11. Demuestre que si L es un lenguaje regular también lo es el lenguaje $L^{\mbox{\scriptsize\it rev}}$ 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 $n\in I\!\!N$ tal que

$$\forall \sigma_1,\sigma_2,\sigma_3:\ \left[\left.\begin{array... ...a_1\tau_1\tau_2^i\tau_3\sigma_3\in L \end{array}\right.\right]$$

14. Utilice el ejercicio anterior para demostrar que el lenguaje $\{0^n1^m2^m\vert m,n\geq 0\}$ no puede ser regular.

15. ¿Cuál es la relación de equivalencia ``$\equiv_L$'', definida según el Teorema de Myhill-Nerode, que en (0+1)^* define el lenguaje $L=\{0^n1^n\vert n\geq 0\}$? Concluya que L no puede ser regular.

16. Demuestre que el lenguaje $L\subset(0+1)^*$ consistente de las cadenas que tiene más 0's que 1's no es regular.

17. Sea $L\subset(0+1+\cdots+9+.)^*$ el lenguaje de palabras que son prefijos (finitos) de la expansión decimal de $\pi$: 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 $\mbox{\it Ent\/}=\{a,b\}$ y sea $\mbox{\it Ent\/}_1=\{bab,abba\}$. Demuestre que todo conjunto que sea regular respecto a $\mbox{\it Ent\/}_1$ también lo es respecto a $\mbox{\it Ent\/}$. Muestre que el recíproco no se cumple: No todo conjunto regular respecto a $\mbox{\it Ent\/}$ lo es respecto a $\mbox{\it Ent\/}_1$.
Siguiente: Programas Un nivel arriba: Expresiones regulares Anterior: Imágenes homomorfas