¿Cuál de los siguientes idiomas sobre ∑ = {a, b} NO está libre de contexto?
(A) {a n segundo yo ⏐ yo ∈ {n, 3n, 5n}, n≥ 0}
(B) {wa n w R segundo norte ⏐ w ∈ {a, b } *, n≥ 0}
(C) {ww R ⏐ w ∈ {a, b}*}
(D) {wa n b n w R ⏐ w ∈ {a, b}*, n≥ 0}
Respuesta: (B)
Explicación: (A): Es CFL, porque tenemos una unión de tres CFL, y las CFL están cerradas bajo propiedad de la unión .
{anbi ⏐ i ∈ {n, 3n, 5n}, n≥ 0} = anbn ∪ anb3n ∪ anb5n
Podemos identificar strings de este lenguaje usando solo una pila.
(B): No es CFL, porque puede identificar strings de un idioma dado usando solo una pila, necesita al menos 2 pilas. Existe una coincidencia de string alternativa que no es posible usando solo una pila. Es un lenguaje sensible al contexto pero no libre de contenido.
(C): Es una LFC muy conocida. Es un lenguaje de palíndromo sobre solo dos alfabetos que se pueden reconocer usando solo una pila.
(D): También es CFL, ya que primero podemos pulsar w, luego a, b pop con a y wR pop con w. Entonces PDA puede aceptar el idioma.
La opción (B) es correcta.
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