PUERTA | PUERTA 2006 | Pregunta 81

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}
¿Cuál de las construcciones podría conducir a un lenguaje no regular?
(A) Tanto I como IV
(B) Solo I
(C) Solo IV
(D) Tanto II como III

Respuesta: (B)
Explicación:  

• repetir (L) no debe confundirse con la concatenación, ya que tiene un orden específico. Solo las mismas strings se concatenan entre sí y no todas. Además, el lenguaje de doble palabra ni siquiera es un CFG [no regular].
• prefijo (L) es un idioma regular: todos los estados en el DFA de L podrían hacerse definitivos, lo que daría como resultado un DFA que aceptaría el prefijo (L) [regular]
• sufijo (L) es un lenguaje normal, ya que se podría construir un NFA que aceptaría el sufijo (L). Cada estado en el DFA de L puede obtener un número de incidente, ventaja desde el estado de inicio, este NFA aceptaría el sufijo (L) [regular].
• half(L) es un lenguaje regular. Es solo un lenguaje que contiene strings de longitud uniforme.

Entonces, la opción (B) es correcta.

Este artículo es una contribución de Aviral Nigam . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geekforgeeks.org o envíe su artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.

Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente. 

Cuestionario de esta pregunta