retagged by
19,919 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

0 votes
0 votes
L1 is DCFL as we can keep pushing a till we encounter end (part 1 of language) or till we encounter b for which we pop a on seeing b. (Part 2 of language).

It cannot be LL(k) as here for any definite value of k we cannot be sure if it's part 1 or part 2 of language. (Cannot have predictive parsing).

So C is correct.
0 votes
0 votes

https://cs.stackexchange.com/q/138479/118790

Check this out and the concept said in Peter Linz. I guess it is much harder to say that whether a LANGUAGE is $LL(k)$ or not while the question is much easier to answer if the grammar is given.

See the $Example$ $7.11$ in Peter Linz, the language from the arguments given by other answers to the GATE question would make it look that the language of the grammar in Example 7.11 is not LL(k) for any $k$ but then suddenly the author comes up with a bit difficult grammar and proves that the problem with the grammar in $ Example$ $7.11$ can be resolved.

So to prove that a language is not $LL(k)$ for any $k$ I feel that much harder work is required.

edited by
0 votes
0 votes

Correct Option is (C).

1. L1 is Regular and L2 is DCFL , and as we know DCFL is closed under union operation with regular set hence L is  DCFL

2. so option b is eliminated.

3. LL(K)  parser needs to determine the next grammar production by seeing the next  input symbols. but here parser is not able to find whether a^n or a^n b^n is to be accepted.

 

Answer:

Related questions

24 votes
24 votes
3 answers
2
Arjun asked Feb 12, 2020
23,427 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,388 views
Raman is confident of speaking English _______six months as he has been practising regularly_______the last three weeksduring, forfor, sincefor, inwithin, for