The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

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

0

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.

Prof. Kamala Krithivasan.

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

+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

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.

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

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 ?

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.

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

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

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.3k
- Engineering Mathematics 5.4k
- Digital Logic 2.1k
- Programming & DS 3.9k
- Algorithms 3.4k
- Theory of Computation 4.2k
- Compiler Design 1.6k
- Databases 3.1k
- CO & Architecture 2.7k
- Computer Networks 3.1k
- Non GATE 1.1k
- Others 1.4k
- Admissions 501
- Exam Queries 449
- Tier 1 Placement Questions 19
- Job Queries 62
- Projects 12

38,000 questions

45,497 answers

131,581 comments

48,635 users