Theory of computations(Grammar)

Question

Consider the grammar:
S->aSbS/ bSaS/ ε,
The smallest string for which the grammar has two derivation trees:

• A. abab
• B. aabb
• C. bbaa
• D. aaabbb

and how?

Comments

In the same way

B. aabb

c. bbaa

Are possible?

Answer 1

Option A
The smallest string that can be derived is abab

S $\rightarrow$ aSbS $\rightarrow$ a[bSaS]bS , now substitute ε in place of S, we will get 'abab'
S $\rightarrow$ aSbS $\rightarrow$ a[ε]bS $\rightarrow$ ab[aSbS] , now substitue ε in place of S, we will get 'abab'

Comments

why can't we simultaneously connect on middle as well as on the right most?

Answer 2

(A)abab       as in second level of derivation tree we have 2 choices to connect bSa either on middle S or on rightmost S