GATE CSE 2020 | Question: 10

Question

Consider the language $L = \{a^{n}\mid n \geq 0\} \cup \{a^{n}b^{n}\mid n \geq 0\}$ and the following statements.

1. $L$ is deterministic context-free.
2. $L$ is context-free but not deterministic context-free.
3. $L$ is not $LL(k)$ for any $k$.

 Which of the above statements is/are TRUE?

• A. Ⅰ only
• B. Ⅱ only 
• C. Ⅰ and Ⅲ only
• D. Ⅲ only

Comments

$L$ is DCFL. A DPDA can be easily constructed.

So, $I$ is True and $II$ is False.

---

The grammar of $L$ would possess non-determinism. If you can only see $aaa$, how would you know it is $aaaa$ or $aaaabbbb$?

No matter how large the lookahead ability you deliver, there will always be some string which has the number of a's larger than the lookahead, for which we couldn't decide what string is it.

So, $III$ is True.

---

thanks I have understood the statement III finally

---

s → K / T / epi

k → aK / epi

T → aTb / epi

first of s is {a,epi}

for ‘a ’ we have two possiblities either s→ K or s→ T both these production will be in same cell that is why not LL(1)

by this easily we can say not LL(K)

Answer 1

$L = \underbrace{\{a^{n}\mid n \geq 0\}}_{L_1} \cup \underbrace{\{a^{n}b^{n}\mid n \geq 0\}}_{L_2}$

Here, $L_1$ is a regular language having regular expression $a^*$ and $L_2$ is a $\text{DCFL}.$ $\text{DCFL}$ is closed under union operator with a regular language as shown below.

$D \cup R = \overline{\overline{ D} \cap \overline {R}}$

Since, $\text{DCFL}$ and regular sets are closed under complement this gives a $\text{DCFL}$ intersection a regular language and $\text{DCFL}$ is closed under intersection with regular set. Ref: https://gatecse.in/closure-property-of-language-families/  

So, $L$ must be deterministic context-free.

---

$LL(k)$ parser needs to determine the next grammar production by seeing the next $k$ input symbols. Now, if we have a string like $a^{k+1}\ldots,$ the parser has no idea whether to pick the production for $a^n$ or $a^nb^n.$ i.e., the input string can be either say $a^{k+10}$ or $a^{k+10}b^{k+10},$ and the $LL(k)$ parser (whatever $LL(k)$ grammar we use for the given language) cannot determine which one it is and so gets stuck. So, the given language is not $LL(k)$ for any $k.$

Reference: https://gatecse.in/lr-parsing-part-2-language-of-ll-and-lr-grammars/

Answer 2

For 1st DCFL is possible.

DCFL is possible and if you are thinking that it is a union of two DCFL language and DCFL is not closed under union and hence it may or may not DCFL then you are wrong if you look closely then first language is regular and DCFL union Regular=DCFL for language first just stay in state q1 and accept every a's because language one is a^n hence it will be accepted and as soon as b is encountered just change the state and pop one a's for every occarance of b...if you get stack symbol (Zo) at last just accept it otherwise reject. DPDA for language

For LL(k) just put K=1 it means it is LL(1) and according to LL(1) property more than one entry can not fill in single column because parser can not distinguish both grammar due to multiple entry.

For a^n FIRST OF a^n contains "a" and for a^n b^n its FIRST OF also contains "a" hence multiple entry in single column so it is not LL(1) and for a^k and a^k b^k so here for same reason, it is not LL(K). LL(K) Parser can not distinguish both grammar.

Hence  Statement 1st and 3rd is correct

So option C is correct.

PS: Here K represents the number of lookaheads. I edited the answer so I hope now it is clear to everyone.

Comments

@Navneet Singh Tomar

here k means the entry?A bit of a confusion here as to what k stands for

---

k stands for look aheads.

---

 In addition to @d3ba comment!

as per the language given in the question we will get the following grammar                                                 

$S$ ->  $aS$|$aSb$|$\epsilon$                                                                                       

and clearly it is not left factored grammar . so, let’s  start from LL(1) (i.e for one lookahead)  for example if we have simply a from the first production and aabb from the second production , then it is not LL(1) due to non left factoring .Similarly if we take LL(k) for any k then also there exist some strings which will fail for LL(k). That’s why III is also true.              

Answer 3

First, Lets check if we can draw a Deterministic PDA for the given language or not.

 

Final state C will accept all strings of the form $a^n$ $b^n$ and final state D will accept all the strings of the form $a^n$ and ϵ.

Hence, the given language is deterministic CFL.

I is true and II is false.

Check for III can be done using a simple argument. In LL(k), k represents the number of lookaheads for LL parser to decide which production should be selected for derivation. Looking at the language, suppose strings are "aaaaa" and "aaaaabbbbb". The parser will not be able to differentiate between these until k > 5. Since, n can be a very large number (possibly infinte), it is simply impossible to use such large value for k. 

Hence, the given language cannot be parsed by a LL(k) parser. 

III is True.

Hence, option (C) is correct.

 

Answer 4

let k=1 so LL(1) we check given language is LL(1) or not , we construct grammar  for a given language                    $S\rightarrow A|B, A\rightarrow aA|\epsilon , B\rightarrow aBb|\epsilon$

    FIRST(A)={a} AND FIRST(B)={a} a IS COMMON in both set so given grammar is not LL(1) parser