The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+30 votes
4.8k views

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
asked in Compiler Design by Loyal (4.3k points)
edited by | 4.8k views
option D correct

2 Answers

+59 votes
Best answer
  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.

answered by Veteran (34.3k points)
edited by
Can u plz explain why is option 2 false it says it produces  all strings with equal no of a's and b's , so how can u reach to conclusion that it is talking about all strings in every form , it simply says that it generates all strings means whatever  strings it generates there  we have equal no of a's and b's ,plz clarify this a bit .

 

Produces  all strings with equal no of a's and b's

In any form they are accepted by grammar. but here aabb, aaabbb not produced by grammar. so false. 

but dpda cannot be constructed for ambiguous grammar isnt it?
Isn't grammer in current form ambiguous so no dpda for it. We need to change grammer fr dpda to accept, but question ask about given grammer . Plz clarify.
No. DPDA is made for language. Parser is made for grammar.

sir , G produces all strings with equal number of a’s and bb’s
implies The strings produced by G are with equal number of a's and b's dont they ? 
i feel it is option D
 

No. Well this is just how the sentence is interpreted in English and has nothing to do with Context free grammar. 

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

Means there is no string with equal number of a's and b's which is not produced by G. But G may produce any other string. 

G only produces strings with equal number of a’s and bb’s

This means G does not produce any string wthich has an unequal numb

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

Had the word  'all ' was not tthere in the question then would the answer be D ?

 

@arjun sir how can an ambiguous grammer be DCFL ?

I didn't fully unserdstand your statement 

No, as long as a context-free language is not inherently ambiguous we can have a DPDA for it. i.e., if the language of a CFG is not inherently ambiguous, we can have an equivalent unambiguous grammar for it and thus construct a DPDA for it.

A grammar is never a language. But an ambiguous grammar can generate a DCFL. Even it can generate a Regular language.
Because for ambiguity, a grammar just needs to produce two different parse trees for some string in L. Even for a regular language we can make a grammar like this.
Also ignore that statement - that is wrong. Even for an unambiguous context-free grammar, we might not be able to get a Deterministic PDA.

Oops..  @arjun sir can u pls make it little more simple ? What you told just now make everything confusing for me .  

 What I knew is a grammer can be 

  • ambiguous
  • inherently ambiguous (ambiguity can be eliminated ) 
  • unambiguous

For Unambiguous Grammer DPAD is possbile .For Inherent Ambiguous  Only NPDA possible 

here the grammer is Ambiguous so no pda is poosible.

Yes, what I told is even if a language is not-deterministic (I used "not" and not "non", because "non-deterministis also includes deterministic by definition), it can have an "unambiguous grammar". For such kind of statelements, an example is necessary. Quoting from Wikipedia:

Unambiguous grammars do not always generate a DCFL. For example, the language of even-length palindromes on the alphabet of 0 and 1 has the unambiguous context-free grammar S → 0S0 | 1S1 | ε. An arbitrary string of this language cannot be parsed without reading all its letters first which means that a pushdown automaton has to try alternative state transitions to accommodate for the different possible lengths of a semi-parsed string

Now, regarding your statements:

A grammer can be 

  • ambiguous -- yes, and the language can be finite, regular, deterministic context-free or non-deterministic context-free
  • inherently ambiguous (ambiguity can be eliminated )  -- not really. The language of a grammar can be inherently ambiguous -- not the grammar.
  • unambiguous -- yes, but no guarantee that the language generated is deterministic context-free.

For Unambiguous Grammer DPDA is possbile -- not always true. Example from Wikipedia shows this.

For Inherent Ambiguous  Only NPDA possible -- true. Because if a language is deterministic context-free, it MUST have an unambiguous grammar (at least one) making the language not inherently ambiguous. For Proof we can take help of Knuth: http://cs.stackexchange.com/questions/109/are-there-inherently-ambiguous-and-deterministic-context-free-languages

Also you may see here:

https://gateoverflow.in/54718/inherently-ambiguous-languages-deterministic-context-grammars

 

Thank you sir

You got it?

Regarding the image - I guess you are confused between $\rightarrow$, $\leftarrow$ and $\leftrightarrow$.

A man is an animal but an animal need not be a man

Likewise a deterministic CFL is not inherently ambiguous. But a not-inherently ambiguous language need not be deterministic context-free. Now using this statement alone one can form numerous questions. But the implication part is more important as that is used in many other subjects and quite easily 10+ marks every GATE depends on if you know it clearly.

@Arjun sir,
I request you to please this question which i asked today at stackexchange
http://cs.stackexchange.com/questions/68455/dcfl-with-prefix-property-have-lr0-grammar

This is about LR and DCFl.
Please see this.
Thnks in advance :)
I think B is also true

it says equal no. of a's and b's and it generates equal no. of a's and b's

 

correct me if I am wrong
@ARSHAD no it will not produce all strings having equal no of a's and b's such as aabb.
According to regular expression DPDA is right. But DPDA is not allowed for ambiguity it's NPDA which handle such issues  while here its working fine. How can it happened ? I am confused regarding this issue.
–2 votes
answer - D
answered by Boss (9.3k points)
The question said that using grammar G's production and then generating string contain equal number of a's and b's not over tha alphabet {a,b}

So in this sense it may be true all three options....

please correct me if I am wrong.....
Answer:

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

33,593 questions
40,128 answers
114,021 comments
38,389 users