PUERTA | PUERTA 2017 MOCK II | Pregunta 40

¿Cuáles de los siguientes lenguajes son regulares sobre ∑ = {a, b}?

L1 = { un ^norte segundo ^norte | 0 < norte ≤ 10}
L2 = { un ²ⁿ | norte ≥ 1}
L3 = { un ^norte! | norte > 0}

(A) L2 solamente.
(B) L1 solamente.
(C) L1 y L2.
(D) Ninguno de L1, L2 y L3.

Respuesta: (C)
Explicación: cualquier idioma para el que tengamos un conjunto finito o para el que posiblemente podamos tener un DFA dibujado es regular.
L1: da un conjunto finito que genera una string con el mismo número de a y el mismo número de b para el rango 0

Por lo tanto, L2 también es regular.

L3: Da todas las strings posibles con a tal que el número de a está en valores factoriales de 1,2,3,4 ……. es decir, {un ¹ , un ² , un ⁶ , un ²⁴ ……………}. El conjunto no es finito ni es posible un DFA para tal conjunto. Por lo tanto, L3 no es regular.

Cuestionario de esta pregunta