Question

Let G=({S},{a,b},R,S) be a context free grammar where the rule set R is
$S\to aSb|SS|ϵ$
Which of the following statements is true?

Answer 1

The grammar is $S\to$ aSb | SS|$ϵ$
(a) G is not ambiguous is false,since $ϵ$ which belongs to L(G),has infinite number of dervation trees,which makes G ambiguous.Some derivation trees are given below


(b) There exists x,y $ϵ$ L(G) such that xy$\text{/}ϵ$ L(G) is false,since $S\to$ SS can be used to denotes xy, whenever x $ϵ$ L(G) and y$ϵ$ L(G)
(c) is true since this language is L(G)={w |$n_a\left(w\right)=n_b\left(w\right)$ and $n_a\left(v\right)\ge n_b\left(v\right)$ where v is any prefix of w} which is equal to ($a^n{b}^n{)}^{\ast }$
This language happens to be a deteministic context free language.
$\therefore$ There exists a DPDA that accepts it.
(d) is false, as the given language is not regular (comparison between number of 'a' s and number of 'b' is there).
$\therefore$ No DFA exists to accept it.