2. La gramática del ejercicio 1, sección 12.3.
3. La gramática del ejercicio 5, sección 12.3.
< A> ::= a<B>|b<S>|b
<B> ::= b<S>|b
con símbolo de inicio < S >
5. <S> ::= a<S>|a< A>|b<C>|a
< A> ::= b< A>|a<C>
<B> ::= a<S>|a
<C> ::= a<B>|a<C>
con símbolo de inicio < S >
6. <S> ::= a< A>|a<B>
< A> ::= b<S>|b
<B> ::= a<B>|a<C>
<C> ::= a<S>|b< A>|a<C>|a
con símbolo de inicio < S >
7. Encuentre autómatas de estado finito que acepten las cadenas de los ejercicios 21 al 29, de la sección 12.4.
8. Elimine los estados que no se alcanzan del autómata de estado finito de la figura 12.5.3 para encontrar un autómata de estado finito equivalente, más sencillo.
9. Demuestre que el autómata de estado finito no determinístico de la figura 12.5.5 acepta una cadena α sobre {a, b} si y sólo si α comienza con bb.
10. Caracterice las cadenas aceptadas por los autómatas de estado finito no determinísticos de las figuras 12.5.7 y 12.5.9.
En los ejercicios 11 al 21, encuentre un autómata de estado finito no determinístico que acepte el conjunto dado de cadenas. Si S1 y S2 son conjuntos de cadenas, sea
S+ 1 ={ u1u2···un |ui ∈ S1, n ∈{1, 2, ...}};
S1S2 ={ uv |u ∈ S1, v ∈ S2}.
11. Ac(A)R, donde A es el autómata del ejercicio 4, sección 12.2
12. Ac(A)R, donde A es el autómata del ejercicio 5, sección 12.2
13. Ac(A)R, donde A es el autómata del ejercicio 6, sección 12.2
14. Ac(A)+, donde A es el autómata del ejercicio 4, sección 12.2
15. Ac(A)+, donde A es el autómata del ejercicio 5, sección 12.2
16. Ac(A)+, donde A es el autómata del ejercicio 6, sección 12.2
Get 12.5.16 exercise solution
17. Ac(A)+, donde A es el autómata de la figura 12.5.7
18. Ac(A1)Ac(A2), donde A1 es el autómata del ejercicio 4, sección 12.2, y A2 es el autómata del ejercicio 5, sección 12.2
19. Ac(A1)Ac(A2), donde A1 es el autómata del ejercicios 5, sección 12.2, y A2 es el autómata del ejercicio 6, sección 12.2
20. Ac(A1)Ac(A1), donde A1 es el autómata del ejercicios 6, sección 12.2
21. Ac(A1)Ac(A2), donde A1 es el autómata de la figura 12.5.7 y A2 es el autómata del ejercicio 5, sección 12.2
22. Encuentre una gramática regular que genere el lenguaje LR, donde L es el lenguaje generado por la gramática del ejercicio 5, sección 12.3.
23. Encuentre una gramática regular que genere el lenguaje L+, donde L es el lenguaje generado por la gramática del ejercicio 5, sección 12.3.
24. Sea L1 (respectivamente, L2) el lenguaje generado por la gramática del ejercicio 5, sección 12.3 (respectivamente, ejemplo 12.5.5). Encuentre una gramática regular que genere el lenguaje L1L2.
25. Demuestre que el conjunto
L ={ x1···xn | x1···xn = xn···x1}
de cadenas sobre {a, b} no es un lenguaje regular.
26. Demuestre que si L1 y L2 son lenguajes regulares sobre Iy S es el conjunto de todas las cadenas sobre I, entonces cada uno de S – L1, L1 ∪L2, L1 ∩L2, L1+ y L1L2 es un lenguaje regular.
27. Demuestre, con un ejemplo, que existen lenguajes libres de contexto L1 y L2 tales que L1 ∩L2 no es libre de contexto.
28. Pruebe o desapruebe: si L es un lenguaje regular, también lo es
{un |u ∈ L, n ∈{1, 2, ...}}.
