Sea L ⊆ ∑* donde ∑ = {a, b}. Cual de los siguientes es verdadero ?
(A) L = { x | x tiene el mismo número de a y b } es regular
(B) L = { a n b n | n ≥ 1 } es regular
(C) L = { x | x tiene más a que b } es regular
(D) L = { a m b n | m? 1, n? 1 } es regular
Respuesta: (D)
Explicación: Para la opción (A) :-
L = { x | x tiene el mismo número de a y b‘s } es regular para la misma cantidad de a y b, necesitamos una pila para almacenar la cantidad de a y empujamos todas las a en la pila y extraemos todas las b para cada a, por lo tanto, a no puede ser lenguaje regular.
Para la opción (B):-
L = { a n b n | n ≥ 1 } es regular tampoco es regular, es lo mismo que el lenguaje anterior. Este lenguaje también dice que el mismo número de a seguido por el mismo número de b, por lo que también necesita una pila para empujar todos los a y sacar todos los b para cada a.
Para la opción (C):-
L= { x | x tiene más a que b } tampoco es regular, también es CFL, necesitamos una pila aquí para que a sea mayor que b.
Para la opción (D):-
L = { a m b n | m ≥ 1, n ≥ 1 } es un lenguaje regular porque no hay restricción de que el mismo número de a y b este lenguaje solo dice que a debe ser seguido por b, por lo tanto, podemos dibujar un DFA para él.
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