Dados dos idiomas:
L 1 = {(ab) n a k | norte > k, k ≥ 0}
L 2 = {un norte segundo metro | n ≠ m}
Usando el lema de bombeo para lenguaje regular, se puede demostrar que
(A) L 1 es regular y L 2 no es regular.
(B) L 1 no es regular y L 2 es regular.
(C) L 1 es regular y L 2 es regular.
(D) L 1 no es regular y L 2 no es regular.
Respuesta: (D)
Explicación: Lenguaje dado L 1 = {(ab) n a k | n > k, k ≥ 0} aquí hay una comparación entre n y k, es decir, n debe ser mayor que k, por lo que necesitamos una pila para realizar cualquier operación de inserción y extracción que pueda resolver mediante PDA y, como sabemos, la comparación no está permitida en un número finito autómatas
Así que no es un lenguaje regular.
Del mismo modo lenguaje L 2 = {a n b m | n ≠ m} aquí necesitamos comparar entre n y m, es decir, m no debe ser igual a n, por lo que nuevamente necesitamos aquí una pila para resolver este PDA.
Y aquí también hay una comparación entre n y m, por lo que no es un lenguaje regular.
La opción (D) es correcta.
Cuestionario de esta pregunta
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA