# GATE2006-32, ISRO2016-35

10.5k 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
–3
option D correct
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.
0
can we say that all DCFL are unambiguous and NDCFL are inherently ambiguous?
4

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

0

@ thanks that cleared many things

1

This is the original question and nowhere $3^{rd}$ production seems to be $\epsilon$. It seems to be a terminal of length 1. Then how grammar can be ambiguous

0
^ is meant to represent lambda, which is another way of writing the null string.

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
6
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
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.
21
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 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.

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

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

0
Can someone please give example for Ambigous grammar generating NCFL..
0

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

@ankitgupta.1729

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

@jatin , yes. right. I have already given one example. You can check Praveen sir's answer for option (C) where language is inherently ambiguous NCFL  here and  here.

0
0

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
This doubt is bit silly but, How a dpda (which accepts language) accepts a Grammar which makes option 2 FALSE.

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

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

## Related questions

1
11.5k views
A CPU generates $32$-bit virtual addresses. The page size is $4$ KB. The processor has a translation look-aside buffer (TLB) which can hold a total of $128$ page table entries and is $4$-way set associative. The minimum size of the TLB tag is: $\text{11 bits}$ $\text{13 bits}$ $\text{15 bits}$ $\text{20 bits}$
The grammar $S\rightarrow AC\mid CB$ $C\rightarrow aCb\mid \epsilon$ $A\rightarrow aA\mid a$ $B\rightarrow Bb\mid b$ generates the language $L=\left \{ a^{i}b^{j}\mid i\neq j \right \}$. In this grammar what is the length of the derivation (number of steps starting from $S$) to generate the string $a^{l}b^{m}$ with $l\neq m$ $\max (l,m) + 2$ $l + m + 2$ $l + m + 3$ $\max (l,m) + 3$
Which one of the following grammars generates the language $L=\left \{ a^{i}b^{j}\mid i\neq j \right \}$? $S\rightarrow AC\mid CB$ $C\rightarrow aCb\mid a\mid b$ $A\rightarrow aA\mid \varepsilon$ $B\rightarrow Bb\mid \varepsilon$ ... $S\rightarrow AC\mid CB$ $C\rightarrow aCb\mid \varepsilon$ $A\rightarrow aA\mid a$ $B\rightarrow Bb\mid b$
Consider the following translation scheme. $S\rightarrow ER$ $R\rightarrow ^{*}E\left \{ print('*'); \right \} R\mid \varepsilon$ $E\rightarrow F+E\left \{ print('+'); \right \}\mid F$ $F\rightarrow (S)\mid id \left \{ print(id.value); \right \}$ Here id is a token that represents an ... $2 * 3 + 4$', this translation scheme prints $2 * 3 + 4$ $2 * +3 \ 4$ $2 \ 3 * 4 +$ $2 \ 3 \ 4+*$