GATE CSE 2006 | Question: 32, ISRO2016-35

Question

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$?

• A. I only
• B. I and III only
• C. II and III only
• D. I, II and III

Comments

two consecutive a or b and vice-versa cannot be generated , since  S -> ab | ba   ; always a&b clubbed up
so Option B false

---

can someone please explain me the iii

---

A  -  Production SS   means it is ambiguous
 

B  -  It states  all  hence we need to find anyone which does not fit, ie. aabb
 

C  -  Grammar and Language are two different things so if we can write the language even of

ambiguous grammar then it is Regular, and if it is Regular then it can be DCFL, CFL, CSL, and many more.

Answer 1

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.

Comments

well, the grammar produce some strings having #a's equals #b's, but the question asks if the grammar can produce all strings having #a's equals #b's which is false.

---

Statement 2 is very confusing

---

Yes because of that I did silly interpretation mistake and ticked "D" lol. Actually it says  "produces all strings with equal a's and b's" which is not same as "all strings produced have equal a's and b's"

Answer 2

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:

Answer 3

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 grammar, not 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

Answer 4

The confusion here is for point 2.

"since grammer itself is ambigious , then option has full right to be ambigious😂"
jokes apart.

 G produces all strings with equal number of a’s and b’s.

this means that can G produce Every possible stirings where we have equal a and b . so Obviously false"aabb".
Had it been like this.

"all strings produced by G has equal a and b " then it'll be correct .

For more clearity , reffer to this comment 
 

 

Answer 5

aabb is not generated which ii is telling
correct ans is i & ii which is option B

Answer 6

I is correct

II is wrong

III is correct