The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+33 votes
6.2k 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 Active (3.7k points)
edited by | 6.2k views
–3
option D correct
+1
yes. You can have a DPDA which puts a A when it reads a 'a' and deletes it when the next 'b' is read. similarly, it can put a 'b" on the stack when a b is read and delete it when the next 'a' is read. In the language generated ab occur together as well as ba. (ii) G is ambiguous. ababab can be generated in 2 ways. You do not talk about a grammar being inherently ambiguous, only a language as inherently ambiguous. Inherently ambiguous CFL can be accepted by NPDA but not DPDA

Prof. Kamala Krithivasan.

2 Answers

+71 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 Boss (31.8k points)
edited by
+4
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 .
+11

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. 

0
but dpda cannot be constructed for ambiguous grammar isnt it?
0
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.
+13
No. DPDA is made for language. Parser is made for grammar.
0

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
 

+10

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

+2

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 ?

 

0

@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.

+2
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.
+1
Also ignore that statement - that is wrong. Even for an unambiguous context-free grammar, we might not be able to get a Deterministic PDA.
0

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.

+11

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

+2
Thank you sir
+1

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.

0
@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 :)
0
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
0
@ARSHAD no it will not produce all strings having equal no of a's and b's such as aabb.
0
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.
0

Arjun Sir, Sorry but I still  have a doubt:

I understand that an unambiguous grammar can either generate a DCFL or a NDCFL.

But, you also wrote the following:

A grammer can be 

  • ambiguous -- yes, and the language can be finite, regular, deterministic context-free or non-deterministic context-free

I am not able to understand the above line. How can an ambiguous grammar be finite, regular, deterministic context-free.

Also, could you please tell what is an ambiguous language? I understand what an ambiguous grammar can be. (The grammar which can one more than parse tree), but I do not know what is an ambiguous language.

 

And also, for the above question, is there an unambiguous grammar available cause it is a regular language?

 

Thank you

 

 

 

–3 votes
answer - D
answered by Loyal (9k points)
+1
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

41,069 questions
47,668 answers
147,405 comments
62,387 users