CGU-NET | UGC NET CS 2016 Julio – III | Pregunta 24

Considere los dos lenguajes siguientes:
L ₁ = {0 ⁱ 1 ^j | mcd (i, j) = 1}
L ₂ es cualquier subconjunto de 0*.
Cual de los siguientes es correcto ?
(A) L ₁ es regular y L ₂ * no es regular
(B) L ₁ no es regular y L ₂ * es regular
(C) Tanto L ₁ como L ₂ * son idiomas regulares
(D) Tanto L ₁ como L ₂ * no son lenguajes regulares

Respuesta: (B)
Explicación: L ₁= {0 ^yo 1 ^j | gcd (i, j) = 1}:
Hay un par infinito que tiene gcd 1. No podemos diseñar FA para ese lenguaje. Es por eso que L ₁ no es regular.
L ₂ es cualquier subconjunto de 0*, podemos construir FA para cualquier subconjunto de un solo alfabeto. Es por eso que L ₂ es regular.
Entonces, la opción (B) es correcta.

Cuestionario de esta pregunta