It will be easy to analyze the problem if we replace terminal $a$ and $b$ by ( and ) respectively.
$S \rightarrow (S) \mid SS \mid \epsilon$
$L(G) =$ balanced parentheses [each left parenthesis has a matching right parenthesis and are well nested ]
example $() , ()(), (()), (()()()).$
- $S \Rightarrow (S) \Rightarrow ()$
$S \Rightarrow SS \Rightarrow S \Rightarrow (S) \Rightarrow ()$
$S \Rightarrow SS \Rightarrow S \Rightarrow (S) \Rightarrow ()$
String $()$ can be derived by above three way each having different derivation tree.
So $G$ is Ambiguous
- Concatenation of two balance parenthesis will be balanced also . eq. $x = (()) \ y= () \ xy= (())()$.
- We can design Deterministic PDA for L. put left parenthesis (only) in stack and pop with right parenthesis.
- We cannot design DFA for L because we need a stack to match left parenthesis with right parenthesis.
only option C is true.