The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+30 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 \} $$

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

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

- I only
- I and III only
- II and III only
- I, II and III

+59 votes

Best answer

**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$.

**False.**$G$ does not produce all strings with equal no. of $a$`s and $b$`s. ($aabb$ cannot be generated).

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

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.

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.

**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

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

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

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 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 :)

- All categories
- General Aptitude 1.2k
- Engineering Mathematics 4.7k
- Digital Logic 1.9k
- Programming & DS 3.5k
- Algorithms 3k
- Theory of Computation 3.7k
- Compiler Design 1.5k
- Databases 2.8k
- CO & Architecture 2.5k
- Computer Networks 2.9k
- Non GATE 835
- Others 1.2k
- Admissions 263
- Exam Queries 390
- Tier 1 Placement Questions 17
- Job Queries 50
- Projects 6

33,593 questions

40,128 answers

114,021 comments

38,389 users