PUERTA | PUERTA-CS-2006 | Pregunta 85 – Part 9

En la gramática correcta de la pregunta anterior , ¿cuál es la longitud de la derivación (número de pasos a partir de S) para generar la string a ^l b ^m con l ≠ m?
(A) max(l,m) + 2
(B) l + m + 2
(C) l + m + 3
(D) max(l, m) + 3

Respuesta: (A)
Explicación:
gramática correcta de la última la pregunta era (D), que es:

S -> AC|CB
C -> aCb|epsilon
A -> aA|a
B -> Bb|b

Ahora, la forma más óptima e intuitiva de generar una string de la forma a ^l b ^m sería usar primero la regla de producción «C -> aCb|epsilon» para obtener tantos a y b como podamos, lo que sería min( l,m). Para obtener el resto de la string, podríamos usar las dos últimas reglas de producción en consecuencia. ^Derivando formalmente la string del formato general a ^lb m de la gramática anterior:

1.      S -> AC 
2.          -> A(aCb) 
3.          -> .... 
4.          -> ....
5.          -> A(am C bm) 
6.          -> A(am bm) 
7.          -> aA(am bm) 
8.          -> .... 
9.          -> ....
10.         -> a(l-m-1)A(am bm) 
11.         -> al bm

Del conjunto anterior de pasos de derivación podemos contar los pasos totales de la siguiente manera:

Production 1 took 1 step       : 1                   [using S->AC]
Production 2-5 took steps      : min(l,m)            [using C->aCb] 
Production 6 took 1 step       : 1                   [using C->epsilon]
Production 7-11 took steps     : max(l,m)-min(l,m)   [using A -> aA|a or B -> Bb|b]
                        
               Total steps   : max(l,m) + 2     

Por lo tanto, la respuesta debería ser (A) : max(l,m) + 2

Esta explicación es aportada por Vineet Purswani.
Cuestionario de esta pregunta