What is the number of steps required to derive the string ((() ()) ()) S → SS…
2014
What is the number of steps required to derive the string ((() ()) ())
S → SS
S → (S)
S → ε
- A.
10
- B.
15
- C.
12
- D.
16
Attempted by 32 students.
Show answer & explanation
Correct answer: A
The grammar generates balanced parentheses. The string ((()())()) contains 5 pairs of parentheses. Each pair requires one S → (S) production (5 total). The innermost empty strings correspond to 3 applications of S → ε. The structure requires 2 concatenations using S → SS to combine the parts. Total derivation steps = 5 (wraps) + 3 (empty) + 2 (concatenations) = 10 steps.