retagged by
28,591 views
64 votes
64 votes

Consider the following statements about the context free grammar

$$G = \left \{ S \rightarrow SS, S \rightarrow ab, S \rightarrow ba, S \rightarrow \epsilon \right \} $$

  1. $G$ is ambiguous
  2. $G$ produces all strings with equal number of $a$’s and $b$’s
  3. $G$ can be accepted by a deterministic PDA.

Which combination below expresses all the true statements about $G$?

  1. I only
  2. I and III only
  3. II and III only
  4. I, II and III
retagged by

4 Answers

Best answer
127 votes
127 votes
  1. True. $G$ is ambiguous. E.g. the string $ab$ has multiple derivation trees like $S \rightarrow SS \rightarrow abS \rightarrow ab$, and $S \rightarrow ab$.
     
  2. False. $G$ does not produce all strings with equal no. of $a$`s and $b$`s. ($aabb$ cannot be generated).
     
  3. True. The given grammar $G$ generates the language $(ab+ba)^*$, which is Regular and therefore also DCFL. So, a D-PDA can be designed for $G$.
     

Hence, the answer is option B.

edited by
3 votes
3 votes

Is ambiguous, as it has two parse tree for the string “abbaba”

G doesn’t product all strings of equal number of a’s and b’s, for ex: string “aabb” doesn’t generate by grammar G.
The language generated by G can be accepted by DPDA. We can notice that grammar G generates, a’s and b’s in pair, i.e. either “ab” or “ba”, so the strings in language are {ab, ba, abab, abba, baba, ….}
We can design the DPDA:

 

2 votes
2 votes

II is definitely false. aabb not generated.


I is true.

$S\rightarrow SS$

$S\rightarrow \epsilon S$

$S\rightarrow \epsilon ba$

$S\rightarrow ba$

--and--

$S\rightarrow SS$

$S\rightarrow S\epsilon$

$S\rightarrow  ba\epsilon$

$S\rightarrow ba$


III is correct.

Even though this grammar is ambiguous, we can translate it into an unambiguous version, and DPDA can accept it.

Being ambiguous is the property of a grammarnot a language.

DPDA can't accept inherently ambiguous languages. (ie the Languages for which there's no unambiguous grammar)

This language is fine.

 

Option B

–3 votes
–3 votes
answer - D
Answer:

Related questions

58 votes
58 votes
7 answers
2
Rucha Shelke asked Sep 26, 2014
27,764 views
Consider the following recurrence:$ T(n)=2T\left ( \sqrt{n}\right )+1,$ $T(1)=1$Which one of the following is true?$ T(n)=\Theta (\log\log n)$$ T(n)=\Theta (\log n)$$ T(n...
51 votes
51 votes
6 answers
3