PUERTA | GATE-CS-2016 (Conjunto 2) | Pregunta 27

Language L1 is defined by the grammar: S1 -> aS1b | ε
Language L2 is defined by the grammar: S2 -> abS2 | ε

Considere las siguientes declaraciones:

P: L1 is regular
Q: L2 is regular

¿Cuál de las siguientes es VERDADERA?
(A) Tanto P como Q son verdaderas
(B) P es verdadera y Q es falsa
(C) P es falsa y Q es verdadera
(D) Tanto P como Q son falsas

Respuesta: (C)
Explicación: L1 tiene la propiedad de que ninguna de las a debe ser igual a ninguna de las b en una string, y todas las a deben preceder a todas las b. Por lo tanto, se requerirá memoria adicional para verificar esta propiedad de una string (Finite Automaton no se puede construir para este tipo de lenguaje). Por lo tanto, este no es un lenguaje regular. Por lo tanto P es Falso.

L2 tiene la propiedad de que ninguno de a debe ser igual a ninguno de b, pero el orden de a y b es diferente aquí, es (ab) *, que no requerirá memoria adicional para ser aceptado. (Finite Automaton se puede construir para este lenguaje). Por lo tanto, L2 es lenguaje regular. Por lo tanto Q es Verdadero.

Cuestionario de esta pregunta