The Gateway to Computer Science Excellence

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

+6

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.

+3

@codingo1234 You can't say

All DCFL's are unambiguous

because "Ambiguity" is a property of a *grammar, *not a language.

What you can say though, is

All DCFG's are unambiguous

because DCFG $\rightarrow \exists $ a DPDA $\rightarrow \exists $ an LR(1) grammar and LR(k) grammars are necessarily unambiguous.

But here's the catch: "Inherent Ambiguity", as opposed to plain "Ambiguity", is a property of a *language, *not a grammar. From Sipser:

As for the question

Are all NDCFL's inherently ambiguous?

The answer is NO. A NDCFL may or may not be inherently ambiguous. That's because a language being NDCF does not mean that it can be generated only by ambiguous grammars. For Example, the language $\{ ww^R \vert w \in (a+b)^* \} $ is non-deterministic (no deterministic PDA exists that can accept it), but it can be generated by the unambiguous grammar $S \rightarrow aSa \vert bSb \vert \epsilon $

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

+5

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 .

+14

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

+13

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.

+7

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.

+17

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

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

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

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

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

0

@surbhijain93 @jatin khachane 1 It is simple.

$S \rightarrow A\; | \; a\; | \;\epsilon$

$A\rightarrow \; a$

It is ambiguous grammar because for string 'a' , There are 2 possible parse trees :- $S\rightarrow A\rightarrow a$ and $S\rightarrow a$ and language is finite. So it is regular, DCFL and NDCFL. After simplification we can write its equivalent unambiguous grammar but originally it is ambiguous. Word 'ambiguous' is associated with grammar and 'inherently-ambiguous' is associated with languages for which no unambiguous grammar is possible.

The equivalent unambiguous grammar for the given question can be :-

$S\rightarrow A\; | B \; | \; \epsilon$

$A\rightarrow abA\; | \; abB\;|\; ab$

$B\rightarrow baB\; | \; baA\;|\; ba$

0

We can say DCFL is NOT inherently ambiguous as there always exits LR(1) grammar for every DCFL which is unambigous..

But this may not be true for NCFL..it may not have atleast one unambigous G for it hence it may /may not be inherently ambigous language

am I right ?

Can you please given one grammar which is ambigous and generating NCFL..(not relevant to ques)

0

@ankitgupta.1729 @Praveen Saini

If a language has an LR(0) grammar iff it is DCFL and has prefix property then is it always unambiguous grammar and inherently unambiguous language.

Please correct me if I wrong.....

0 votes

II is definitely false. aabb not generated.

I is true.

$S\rightarrow SS$

$S\rightarrow \epsilon S$

$S\rightarrow \epsilon ba$

$S\rightarrow ba$

--and--

$S\rightarrow SS$

$S\rightarrow S\epsilon$

$S\rightarrow ba\epsilon$

$S\rightarrow ba$

III is correct.

Even though this grammar is ambiguous, we can translate it into an unambiguous version, and DPDA can accept it.

Being ambiguous is the property of a * grammar, *not a language.

DPDA can't accept *inherently ambiguous* ** languages**. (ie the Languages for which there's no unambiguous grammar)

This language is fine.

**Option B**

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.6k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.5k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,833 questions

57,748 answers

199,477 comments

108,137 users