PUERTA | PUERTA 2006 | Pregunta 82

Sea L un lenguaje regular. Considere las construcciones en L a continuación:
repetir (L) = {ww | w ∊ L}
prefijo (L) = {u | ∃v : uv ∊ L}
sufijo (L) = {v | ∃u uv ∊ L}
mitad (L) = {u | ∃v : | v | = | tu | y uv ∊ L}
¿Qué elección de L es la más adecuada para respaldar su respuesta anterior?
(A) (a + b)*
(B) {ϵ, a, ab, bab}
(C) (ab)*
(D) {a ⁿ b ⁿ | n ≥ 0}

Respuesta: (A)
Explicación:  

Un contraejemplo que pruebe todas las conclusiones de la última pregunta de una sola vez debería tener las siguientes propiedades:

• L debe ser regular debido a la demanda de la pregunta
• L debería ser un conjunto infinito de strings, de lo contrario, la mitad (L) sería regular
• L debe tener más de un alfabeto en su gramática, de lo contrario repetir (L) sería regular.

Por lo tanto,

1. (a + b)* es un ejemplo perfecto para respaldar las conclusiones de la última pregunta. Es regular, tiene más de un alfabeto y es un conjunto infinito.
2. {ϵ, a, ab, bab} es un conjunto finito, por lo tanto incorrecto.
3. (ab)* es equivalente a c∗, que es un idioma alfabético, por lo tanto incorrecto.
4. { un ^segundo norte ^| n ≥ 0} ni siquiera es un lenguaje regular, por lo tanto incorrecto.

Esta solución es aportada por .
Cuestionario de esta pregunta