PUERTA | PUERTA CS 2018 | Pregunta 46

Considere los siguientes idiomas:

I. {a ^metro segundo norte c ^pag re ^q ∣ ^metro + pag = norte + q, donde metro, norte, pag, q ≥ 0} II. {a ^metro segundo norte c ^pag re ^q ∣ ^metro = norte y pag = q, donde metro, norte, pag, q ≥ 0} III. {a ^metro segundo norte c ^pag re ^q ∣ ^metro = norte = pag y pag ≠ q, donde metro, norte, pag, q ≥ 0} IV. {a ^metro segundo norte c ^pags re ^q ∣ ^mn = pags + q, donde metro, norte, pags, q ≥ 0}

¿Cuáles de los lenguajes anteriores son libres de contexto?

(A) Solo I y IV
(B) Solo I y II
(C) Solo II y III
(D) Solo II y IV

Respuesta: (B)
Explicación: I. {a ^m b ⁿ c ^p d ^q ∣ m + p = n + q, donde m, n, p, q ≥ 0}

m + p = n + q can also be written as m-n = q-p.

Ver las strings en el idioma dado: {ε ab, ad, bc, cd, abcd, abbc, aabb, aadd, acdd, bbcc, ccdd, aaabdd, aaabbd, bcccdd, aabcdd, ………….}

El lenguaje dado es libre de contexto, por lo que Push Down Automata puede diseñarse para esto.
 
II. {a ^metro segundo norte c ^pag re ^q ∣ ^metro = norte y pag = q, donde metro, norte, pag, q ≥ 0}

m = n and p = q

Vea las strings en el idioma dado: { ε, ab, cd, abcd, aabbcd, abccdd, aaabbbccdd, …………}
Definitivamente libre de contexto, por lo tanto, PDA puede diseñarse para esto.
 

tercero m=n=pyp ≠ q. No libre de contexto.

IV. mn = p+q, no libre de contexto.

La opción (B) es correcta.

Cuestionario de esta pregunta