What is the number of steps required to derive the string ((() ()) ()) for the following grammar? S → SS S → (S) S → ϵ

What is the number of steps required to derive the string ((() ()) ()) for the following grammar? S → SS S → (S) S → ϵ Correct Answer 10

The correct answer is "option 1".

EXPLANATION:

The given grammer is:

S → SS

S → (S)

S → ϵ

To derive string ((() ()) ()) using left derivation, steps are:

1.S → (S)                                    // S → (S)

2.S → (SS)                                 // S → SS

3.S → ((S)S)                              // S → (S)

4.S → ((SS)S)                           // S → SS

5.S → (((S)S)S)                        // S → (S)

6.S → (((S)(S))S)                     // S → (S)

7.S → (((S)(S))(S))                  // S → (S)

8.S → ((()(S))(S))                    // S → ϵ

9.S → ((()())(S))                      // S → ϵ

10.S → ((()())())                      // S → ϵ

Hence, the number of steps required to derive the string ((() ()) ()) is 10. 

Additional Information

There are two types of derivations:

1.Rightmost derivation: Deriving a string by expanding the rightmost terminal.

2.Left most derivation: Deriving a string by expanding the leftmost terminal.