PUERTA | PUERTA-CS-2001 | Pregunta 31

Considere los siguientes idiomas




¿Cuáles de los idiomas son regulares?
(A) Solo L1 y L2
(B) Solo L2, L3 y L4
(C) Solo L3 y L4
(D) Solo L3

Respuesta: (D)
Explicación: Un lenguaje se conoce como lenguaje regular si existe un autómata finito (no importa si es determinista o no determinista) que lo reconoce. Entonces, si para un lenguaje dado, podemos llegar a un autómata finito, podemos decir que el lenguaje es regular. Pero a veces, no es del todo obvio diseñar un autómata correspondiente a un lenguaje dado, pero seguramente existe. En ese caso, no deberíamos empezar a pensar que el lenguaje dado no es regular. Deberíamos usar el lema de bombeopara decidir si el lenguaje dado es regular o no.

Según el lema de bombeo,

“Supongamos que L es un lenguaje regular, entonces existe al ≥ 1 tal que para toda string s ∈ L, donde |s| ≥ l, siempre podemos dividir s (existe al menos una división de este tipo) de tal manera que s se puede escribir como xyz con |xy| ≤ l y y ≠ ε y para todo i ≥ 0 , xy ⁱ z ∈ L”. l se conoce como longitud de bombeo.

Reformulemos el lema dado para lenguajes no regulares. Supongamos que L es un lenguaje, si para todo l ≥ 1 existe una string s ∈ L con |s| ≥ l tal que para todo desdoblamiento (no existe un solo desdoblamiento que no siga esta regla) de s en forma de xyz tal
que |xy| ≥ l y y ≠ ε , existe un i≥ 0 tal que xy ⁱ z ∉ L, entonces L no es regular. Nótese que aquí enfatizamos en encontrar tales s si queremos probar que un lenguaje no es regular.

Elección de las preguntas:

(a) En la opción 1 , primero consideremos que w tiene una longitud n y contiene solo a. En este caso el lenguaje representa a ⁿ a ⁿ . La longitud de la string representada por language debe ser par. Considere l = n, luego xyz = a ⁿ a ⁿ con xy = a ⁿ . supongamos y = a, luego consideremos la pertenencia de xy ⁱ z con i = 0. Esto simplemente tendrá una longitud impar que no pertenece a L. Entonces L no es regular. Para discutirlo con más detalle, consideremos otro ejemplo. Supongamos que w = a ^p b, entonces la cuerda formada por L será a ^p ba ^p b que tiene una longitud de 2p + 2. Supongamos que l = p, entonces xy = a ^p. supongamos y = a, luego considere la pertenencia de xy ⁱ z con i = 0. Esto ciertamente no pertenece a L. Entonces L no es regular.

(b) En la opción 2 , el primer ejemplo funcionará como arriba. En el segundo ejemplo, la string será a ^p bba ^p y no habrá cambios en el proceso para demostrar que no es regular.

(c) En la opción 3 , suponiendo que estamos considerando un número entero de 0 y 0 ^2∗n da como resultado una string vacía, que también se acepta, podemos simplemente construir un DFA como se indica a continuación. Simplemente acepta una string si está vacía o contiene un número par de ceros. Así que el lenguaje es regular.

(d) En la opción 4 , simplemente podemos suponer que la longitud de bombeo l =i ² /2. Ahora considere el xy = 0 ^l con y = 0, ahora si verificamos la pertenencia de xy ² z, podemos encontrar que esto representará 0 ^{i^2} +1, y correspondiente al cual no existe j tal que
j ² = i ² + 1 donde i y j son enteros excepto j = 1 e i = 0. Pero como i no puede ser cero. En resumen, utilizando el lema de bombeo, podemos generar 0 ^{i^2} +1 así como 0 ^{i^2} -1, que no estarán disponibles en L.

Entonces L no es regular.

Esta explicación ha sido aportada por Durgesh Pandey.
Cuestionario de esta pregunta