ISRO | CS ISRO 2014 | Pregunta 5 – Part 8

¿Cuál es el número de pasos necesarios para derivar la string ((()())())

S → SS
S → (S)
S → ε

(A) 10
(B) 15
(C) 12
(D) 16

Respuesta: (A)
Explicación: Para generar ((()())()) , se necesitan los siguientes pasos:

1) S → (S)
2) S → (SS)
3) S → ((S)S)
4) S → ((SS)S)
5) S → (((S)S))S)
6) S → (((S)(S))S)
7) S → (((S)(S))(S))  [S → ε]  
8) S → ((()(S))S)     [S → ε]
9) S → ((()())S)      [S → ε]  
10) S → ((()()))

La opción (A) es correcta.
Cuestionario de esta pregunta