Dados los dos idiomas siguientes:
L1 = {a n b n | norte ≥ 0, norte ≠ 100}
L2 = {w ∈ {a, b, c}*| n a (w) = n b (w) = n c (w)}
¿Cuál de las siguientes opciones es correcta?
(A) Tanto L 1 como L 2 no son lenguajes libres de contexto
(B) Tanto L 1 como L 2 son lenguajes libres de contexto.
(C) L 1 es lenguaje libre de contexto, L 2 no es lenguaje libre de contexto.
(D) L 1 no es lenguaje libre de contexto, L 2es un lenguaje libre de contexto.
Respuesta: (C)
Explicación: Idioma L1 = {a n b n | n ≥ 0, n ≠ 100} es independiente del contexto porque empujamos todos los a^n en la pila y extraemos todos los elementos b^n para cada elemento a^n, ya que podemos comparar todos los a y b aquí usando solo una pila.
Pero lenguaje L2 = {w ∈ {a, b, c}*| n a (w) = n b (w) = n c (w)} no es un lenguaje libre de contexto porque no podemos comparar todos los a, b y c simultáneamente con la ayuda de una sola pila para esto, necesitamos más de una pila aquí entonces este lenguaje L2 se convierte en lenguaje sensible al contexto.
La opción (C) 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