Automatas

Ejercicio 1- Define, de manera recursiva, el lenguaje L de las cadenas de paréntesis correctas.
(Es decir, (())() ∈ L, ()(() ∉ L)
SOLUCIÓN:
1. ()∈ L (aunque λ∉ L, se puede consideraralternativamente que λ ∈ L para definir con 2 y 3 las demás palabras).
2. Si x ∈ L, entonces (x) ∈ L .
3. Si x, y ∈ L, entonces x y ∈ L.
4. No hay más palabras en L que las formadas por las reglasanteriores.

Ejercicio 2- Encuentra una expresión regular correspondiente al lenguaje de las cadenas en {a, b}* que no empiezan por b y no contienen dos a’s consecutivas. Construye un AFN-λ reconocedor deeste lenguaje.
Una ER que describe el lenguaje es λ+a(b+ba)*. El AFN-λ se puede construir directamente utilizando el Teorema de Kleene.

Ejercicio 3 (a) Define, mediante expresiones regulares,las clases de equivalencia respecto a la relación de distinguibilidad con respecto al lenguaje del ejercicio anterior, utilizando para ello un conjunto distinguible máximo.
(b) Define completamentela operación de concatenación por la derecha de las clases con las letras del alfabeto.
(c) Define a partir de (a) y (b) el AF mínimo.
SOLUCIÓN:
(a) Para encontrar un CDM, vamos estudiando lasdistintas palabras del lenguaje. Empezamos comparando las palabras de longitud 1 con la palabra vacía y entre sí. Es fácil ver que {λ, a} es un conjunto distinguible (z = a). También son distinguibles{λ, b} (z = a) y {a, b} (z = b). Por tanto, {λ, a, b} es un conjunto distinguible.
(b) En cuanto a las palabras de longitud 2, es fácil ver que aa es indistiguible de b, que ba es indistinguible de by que bb es indistinguible de b (son palabras que no están en el lenguaje y que, seguidas de cualquier cola, tampoco), mientras que ab es distinguible de λ , a y b.

Con esto, es sencillo darsecuenta que si w es una palabra de longitud mayor o igual que 3, resulta que:
(c) si w empieza por a, acaba por a y no contiene la subcadena aa, entonces es indistinguible de a,
(d) si w empieza...