PUERTA | GATE-CS-2015 (Conjunto 2) | Pregunta 61

¿Cuál de los siguientes idiomas es/son regulares?

L1: {wxwR ⎪ w, x ∈ {a, b}* and ⎪w⎪, ⎪x⎪ >0} wR is the reverse of string w
L2: {anbm ⎪m ≠ n and m, n≥0
L3: {apbqcr ⎪ p, q, r ≥ 0}  

(A) Solo L1 y L3
(B) Solo L2
(C) Solo L2 y L3
(D) Solo L3

Respuesta: (A)
Explicación:

L3 is simple to guess, it is regular.
Below is DFA for L1.



L1 is interesting. The important thing to note 
about L1 is length of x is greater than 0, i.e.,
|x| > 0.
So any string than starts and ends with same character
is acceptable by language and remaining string becomes w.
Below is DFA for L1.

Cuestionario de esta pregunta