PUERTA | GATE-CS-2017 (Conjunto 1) | Pregunta 34

Considere la siguiente gramática libre de contexto sobre el alfabeto ∑ = {a, b, c} con S como símbolo de inicio:

S → abScT | abcT
T → bT | b

¿Cuál de los siguientes representa el lenguaje generado por la gramática anterior?
(A) {(ab) ^norte (cb) ^norte | norte >= 1 }
(B) {(ab ^norte cb ^{metro ₁} cb ^{metro ₂} …cb ^{metro _norte} | norte, metro ₁ , metro ₂ , ….., metro _norte >= 1 }
(C) {(ab) ^norte ( cb ^m ) ⁿ | n >= 1 }
(D) {(ab) ⁿ (cb ⁿ ) ^m | m, n >= 1 }

Respuesta: (B)
Explicación:Generemos una string a partir de la gramática dada:

S → abscT
→ ab abscT cT
→ abab abcT cTcT
→ abababc bT cTcT
→ abababcb bT cTcT
→ abababcbb bT cTcT
→ abababcbbbb cTcT
→ abababcbbbbc b cT
→ abababcbbbbcbc bT
→ abababcbbbbcbcbb

Esta string puede descartar todas las opciones incorrectas. Ahora intentemos analizar esta string.

→ abababcbbbbcbcbb

→ {(ab ^norte cb ^{metro ₁} cb ^{metro ₂} …cb ^{metro _norte} | norte, metro ₁ , metro ₂ , ….., metro _norte >= 1 }

Podemos descartar claramente la opción (A), (C) y (D) con la ayuda de la string generada por la gramática dada.

Sólo la opción (B) es correcta.

Cuestionario de esta pregunta