¿Cuáles de los siguientes son libres de contexto?
A = {anbnambm | m, n>=0}
B = {ambnambn | m, n>=0}
C = {ambn | m≠2n,m, n>=0}
(A) Solo A y B
(B) Solo A y C
(C) Solo B y C
(D) Solo C
Respuesta: (B)
Explicación: Primero verifique A:-
a^n & b^n y a^m & b^m debe ser comparable usando una pila para CFL . Empuje todos los a ^ n en la pila, luego extraiga todos los b ^ n para cada a ^ n si en la parte inferior de tener nulo a y b ambos son iguales, compare a ^ m y b ^ m se puede comparar como empujar a ^ m en la pila y pop b^m para cada a^m , por lo tanto, es un lenguaje libre de contexto.
Para B: –
Esto no se puede hacer en una sola pila porque m y n no son comparables, no podemos encontrar cuándo presionar o cuándo abrir, por lo que necesitamos aquí más pila, por eso este es un lenguaje sensible al contexto.
Para C:-
También es un lenguaje libre de contexto porque primero crea el autoamata para el lenguaje a^mb^n| m = 2n luego haga el estado final como estado no final y no final como final.
La opción (B) 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