The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+1 vote

$L=\{x^n:n \in N\} \cup\{x^ny^n|n \in N\}$

This language does not have LL(k) parser while being deterministic context free.Why?

This language does not have LL(k) parser while being deterministic context free.Why?

0

If we assume end delimiter is there

then it is DCFL, in that case it should have LL(k) for some k

right sir ?

then there is no meaning in this question !

0

if it is LL(k) for some k, then it is LR(m) for some m. but converse not true !

Forgot that basic point, thanks sir !!

+1

@Arjun sir and @Shaik Masthan-I am trying to build a proof point out if anywhere I go wrong.

The grammar can be

$S->A|B\\A->xA|x\\B->xBy|xy$

For string let's say $w_1=x^3$ we need to use production $S->A$ and for string $w_2=x^3y^3$ we need to use the production $S->B$

So here we are in a dilemma which one to use.

Similarly, for a given string of length say $n$, we are not sure how much of lookahead we need for each string so that production to be used at each step can be uniquely determined.

So, the given language does not have an LL(K) parser for any fixed k.

Am I going in the correct direction?

+1

I don't know a formal way. But the above reason by @Ayush Upadhyaya is sufficient.

https://stackoverflow.com/questions/14674912/why-are-there-lr0-parsers-but-not-ll0-parsers

- All categories
- General Aptitude 1.8k
- Engineering Mathematics 7.3k
- Digital Logic 2.9k
- Programming & DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6k
- Compiler Design 2k
- Databases 4.1k
- CO & Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.4k
- Others 1.4k
- Admissions 596
- Exam Queries 577
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

49,532 questions

54,123 answers

187,320 comments

71,044 users