retagged by
19,900 views
29 votes
29 votes

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?

  1. Ⅰ only
  2. Ⅱ only 
  3. Ⅰ and Ⅲ only
  4. Ⅲ only
retagged by

7 Answers

Best answer
16 votes
16 votes

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

29 votes
29 votes

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.

9 votes
9 votes

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.

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.

 

6 votes
6 votes
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
Answer:

Related questions

24 votes
24 votes
3 answers
2
Arjun asked Feb 12, 2020
23,414 views
Which one of the following regular expressions represents the set of all binary strings with an odd number of $1’$s?$((0+1)^*1(0+1)^*1)^*10^*$$(0^*10^*10^*)^*0^*1$$10^*...
17 votes
17 votes
3 answers
3
31 votes
31 votes
4 answers
4
Arjun asked Feb 12, 2020
7,386 views
Raman is confident of speaking English _______six months as he has been practising regularly_______the last three weeksduring, forfor, sincefor, inwithin, for