in Theory of Computation retagged by
13,878 views
17 votes
17 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
in Theory of Computation retagged by
by
2441 3624 5537
13.9k views

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

15
15
thanks I have understood the statement III finally
0
0
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)
0
0

Subscribe to GO Classes for GATE CSE 2022

6 Answers

6 votes
6 votes
 
Best answer

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

by
513 804 798
17 votes
17 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.

edited by
by
2 5 8

5 Comments

With your grammer we can get string "aab" which is not accepted by L .

So i think your grammer is wrong.
0
0

@Navneet Singh Tomar

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

0
0
k stands for look aheads.
0
0

 In addition to @d3ba comment!

as per the language given in the question we will get the following grammar                                                 S->aS|aSb|eps                                                                                         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.              

1
1
8 votes
8 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.

 

4 votes
4 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
by
5 41 74
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.
by
27 61 153
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
by
1
Answer:

Related questions