5.7k 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
edited | 5.7k views
–3
option D correct

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
+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 .
+10

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.
+11
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.

+10

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

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