Construir un autómata finito determinista equivalente al dado.
Solución:
Nota: R es el “estado trampa” que puede ser omitido.
------------------------------------------------------------------------------------------------------------------------------
Razonar si los siguientes lenguajes son regulares:
a) {𝑎𝑎𝑛𝑛 𝑏𝑏 𝑚𝑚 ∶ 𝑛𝑛 > 𝑚𝑚 ∨ 𝑛𝑛 < 𝑚𝑚}.
b) {𝑎𝑎𝑛𝑛 𝑏𝑏 𝑚𝑚 ∶ 𝑛𝑛 ≥ 𝑚𝑚 ∨ 𝑛𝑛 ≤ 𝑚𝑚}.
c) {𝑎𝑎𝑛𝑛 𝑏𝑏 𝑚𝑚 ∶ 𝑛𝑛 > 𝑚𝑚 ∧ 𝑛𝑛 < 𝑚𝑚}.
d) {𝑎𝑎𝑛𝑛 𝑏𝑏 𝑚𝑚 ∶ 𝑛𝑛 ≥ 𝑚𝑚 ∧ 𝑛𝑛 ≤ 𝑚𝑚}.
e) {𝑤𝑤 ∈ {𝑎𝑎, 𝑏𝑏}∗ ∶ 𝑎𝑎𝑎𝑎𝑎𝑎 = 𝑤𝑤𝑤𝑤𝑤𝑤}.
Solución:
a) No regular, ya que es equivalente a {𝑎𝑎𝑛𝑛 𝑏𝑏 𝑚𝑚 : 𝑛𝑛 ≠ 𝑚𝑚} = 𝑎𝑎∗ 𝑏𝑏 ∗ − {𝑎𝑎𝑛𝑛 𝑏𝑏 𝑛𝑛 ∶ 𝑛𝑛 ≥ 0}.
b) Regular. Equivalente a la expresión regular 𝑎𝑎∗ 𝑏𝑏 ∗ .
c) Regular. El lenguaje es vacío.
d) No regular. Es equivalente al lenguaje {𝑎𝑎𝑛𝑛 𝑏𝑏 𝑛𝑛 ∶ 𝑛𝑛 ≥ 0}.
e) Regular. Es equivalente a la expresión regular 𝑎𝑎(𝑏𝑏𝑏𝑏)∗ .
------------------------------------------------------------------------------------------------------------------------------
Construir una gramática regular sobre el alfabeto Σ = {𝑎𝑎, 𝑏𝑏} que genere todas las palabras que
contienen como máximo tres símbolos 𝑎𝑎. Escribir la derivación de la palabra 𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏.
Solución:
𝑆𝑆 → 𝑏𝑏𝑏𝑏 | 𝑎𝑎𝑎𝑎 | 𝜀𝜀
𝐴𝐴 → 𝑏𝑏𝑏𝑏 | 𝑎𝑎𝑎𝑎 | 𝜀𝜀
𝐵𝐵 → 𝑏𝑏𝑏𝑏 | 𝑎𝑎𝑎𝑎 | 𝜀𝜀
𝐶𝐶 → 𝑏𝑏𝑏𝑏 | 𝜀𝜀
𝑆𝑆 ⇒ 𝑏𝑏𝑏𝑏 ⇒ 𝑏𝑏𝑏𝑏𝑏𝑏 ⇒ 𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏 ⇒ 𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏 ⇒ 𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏 ⇒ 𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏 ⇒ 𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏 ⇒ 𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏
------------------------------------------------------------------------------------------------------------------------------
Se considera el alfabeto Σ = {0,1}. Construir autómatas finitos deterministas que reconozcan
los siguientes lenguajes:
a) 𝐿𝐿1 = {𝑥𝑥 ∶ 𝑥𝑥 contiene un número impar de 0 y un número par de 1}
b) 𝐿𝐿2 = {𝑥𝑥 ∶ 𝑥𝑥 contiene un número par de 0 y un número par de 1}
c) 𝐿𝐿3 = {𝑥𝑥 ∶ 𝑥𝑥 contiene un número impar de 0 y un número impar de 1}
Solución: Apartado a)
Apartados b) y c): Cambiar el estado final 𝑞𝑞3 por 𝑞𝑞0 y 𝑞𝑞2 respectivamente.
------------------------------------------------------------------------------------------------------------------------------
Minimizar el autómata de la figura y hallar el lenguaje que reconoce.
Solución: El autómata mínimo es
y, por tanto, el lenguaje reconocido es (𝑎𝑎 | 𝑏𝑏𝑏𝑏)∗ .
------------------------------------------------------------------------------------------------------------------------------
Sea Σ un alfabeto dado y sea 𝐿𝐿 ⊂ Σ ∗ un lenguaje regular. Consideramos el lenguaje
𝐿𝐿1 = {𝑥𝑥𝑥𝑥 ∶ 𝑥𝑥 ∈ 𝐿𝐿, 𝑦𝑦 ∉ 𝐿𝐿}
• Justificar por qué 𝐿𝐿1 es un lenguaje regular.
• Probar que el recíproco no es cierto en general, esto es, el hecho de que 𝐿𝐿1 sea un lenguaje
regular no implica necesariamente que 𝐿𝐿 tenga que serlo.
Solución:
• 𝑦𝑦 ∉ 𝐿𝐿 significa que 𝑦𝑦 ∈ 𝐿𝐿𝑐𝑐 , que también es un lenguaje regular por la propiedades de cierre.
Ahora 𝐿𝐿1 = 𝐿𝐿 ⋅ 𝐿𝐿𝑐𝑐 es un lenguaje regular al ser concatenación de dos lenguajes regulares.
• Sea el lenguaje no regular 𝐿𝐿 = {𝑎𝑎𝑛𝑛 ∶ 𝑛𝑛 es primo} entonces 𝐿𝐿𝑐𝑐 = {𝑎𝑎𝑛𝑛 ∶ 𝑛𝑛 no es primo}, y en
consecuencia 𝐿𝐿1 = 𝐿𝐿 ⋅ 𝐿𝐿𝑐𝑐 = {𝑎𝑎𝑛𝑛+𝑚𝑚 ∶ 𝑛𝑛 es primo, 𝑚𝑚 no es primo} = {𝑎𝑎𝑛𝑛 ∶ 𝑛𝑛 ≥ 2}, que es
regular.
------------------------------------------------------------------------------------------------------------------------------
Se considera la gramática 𝐺𝐺 = (Σ, 𝑁𝑁, 𝑆𝑆, 𝑃𝑃), donde Σ = {𝑎𝑎, 𝑏𝑏}, 𝑁𝑁 = {𝑆𝑆, 𝐴𝐴𝑛𝑛 , 𝐴𝐴𝑛𝑛−1 , … , 𝐴𝐴0 } es un
conjunto de 𝑛𝑛 + 2 variables (𝑛𝑛 ≥ 0) y 𝑃𝑃 es el conjunto de producciones:
𝑆𝑆 → 𝐴𝐴𝑛𝑛
𝐴𝐴𝑛𝑛 → 𝐴𝐴𝑛𝑛−1 𝐴𝐴𝑛𝑛−1
𝐴𝐴𝑛𝑛−1 → 𝐴𝐴𝑛𝑛−2 𝐴𝐴𝑛𝑛−2
⋮
𝐴𝐴1 → 𝐴𝐴0 𝐴𝐴0
𝐴𝐴0 → 𝑎𝑎 | 𝑏𝑏
¿Es ℒ(𝐺𝐺) un lenguaje regular para un 𝑛𝑛 ≥ 0 fijo? ¿Por qué?
Solución:
𝑛𝑛
Puesto que 𝑛𝑛 es fijo, el lenguaje es ℒ(𝐺𝐺) = (𝑎𝑎 | 𝑏𝑏)2 , que es finito y por tanto regular.
------------------------------------------------------------------------------------------------------------------------------
Se considera el lenguaje 𝐿𝐿 = {𝑥𝑥𝑥𝑥 ∈ {𝑎𝑎, 𝑏𝑏}∗ ∶ |𝑥𝑥| = |𝑦𝑦|, |𝑥𝑥|𝑎𝑎 = |𝑦𝑦|𝑏𝑏 }.
• Describir con exactitud las palabras de 𝐿𝐿.
• Se sabe que la intersección de dos lenguajes regulares es un lenguaje regular. Usar esta
propiedad para concluir que 𝐿𝐿 no es un lenguaje regular.
• Hallar una gramática 𝐺𝐺 tal que 𝐿𝐿 = ℒ(𝐺𝐺).
Solución:
• Puesto que |𝑥𝑥| = |𝑦𝑦|, las palabras de 𝐿𝐿 son cadenas de longitud par tal que el número de
𝑎𝑎’s de la primera mitad de la cadena coincide con el número 𝑏𝑏’s de la segunda.
• Basta observar que 𝐿𝐿 ∩ 𝑎𝑎∗ 𝑏𝑏 ∗ = {𝑎𝑎𝑛𝑛 𝑏𝑏 𝑛𝑛 ∶ 𝑛𝑛 ≥ 0}, por tanto 𝐿𝐿 no puede ser regular por las
propiedades de cierre.
• 𝑆𝑆 → 𝜀𝜀│𝑎𝑎𝑎𝑎𝑎𝑎│𝑏𝑏𝑏𝑏𝑏𝑏│𝑆𝑆𝑆𝑆
------------------------------------------------------------------------------------------------------------------------------
a) Se considera el alfabeto Σ = {𝑎𝑎, 𝑏𝑏} y la expresión regular 𝛽𝛽 = (𝑎𝑎 | 𝑏𝑏 + 𝑎𝑎)∗ . Hallar el autómata
finito determinista mínimo que reconoce el lenguaje ℒ(𝛽𝛽) generado por la expresión 𝛽𝛽.
b) Describir someramente el lenguaje ℒ(𝑎𝑎 · 𝛽𝛽) = {𝑎𝑎𝑎𝑎 ∶ 𝑥𝑥 ∈ ℒ(𝛽𝛽)} . ¿Existe alguna propiedad
que identifique con precisión ℒ(𝑎𝑎 · 𝛽𝛽)? Justificar la respuesta.
c) Sea 𝑥𝑥 ∈ Σ ∗ cualquier palabra y definamos
|𝑥𝑥|𝑎𝑎𝑎𝑎 = número de subpalabras 𝑎𝑎𝑎𝑎 que contiene 𝑥𝑥,
|𝑥𝑥|𝑏𝑏𝑏𝑏 = número de subpalabras 𝑏𝑏𝑏𝑏 que contiene 𝑥𝑥.
Consideramos el lenguaje 𝐿𝐿 = {𝑥𝑥 ∈ Σ ∗ : |𝑥𝑥|𝑎𝑎𝑎𝑎 = |𝑥𝑥|𝑏𝑏𝑏𝑏 }. Construir un autómata finito 𝑀𝑀 tal
que 𝐿𝐿 = ℒ(𝑀𝑀).
Solución:
a) El autómata mínimo es
b) ℒ(𝑎𝑎 ⋅ 𝛽𝛽) son las palabras que comienzan por 𝑎𝑎 y que contienen el mismo número de
subpalabras 𝑎𝑎𝑎𝑎 y 𝑏𝑏𝑏𝑏.
c) El autómata puede ser
