in Theory of Computation recategorized by
644 views
0 votes
0 votes

i am getting a option 

in Theory of Computation recategorized by
644 views

15 Comments

Whats the answer given ?
0
0
language generated by above grammar is WW$^R$ which is unambiguous but it is not DCFL

there exist a one-to-one correspondence between DCFL and LR(K) parsers

So all options are wrong.

Post the solution image which they given
0
0
Option c ??
0
0

there exist a one-to-one correspondence between DCFL and LR(K) parsers

plzz ellaborate it

0
0
i mean to say, if it is DCFL, then it must be parsed by some LR(K) parser.

and

if it is parsed by some LR(K) parser, then it must be have a DCFL.
1
1
Shaikh bro answer is a)
And why it is not cfg definitely it is cfg
S ⇒ aSa |  bSb | aSb | bSa |ε
It is cf grammer for even length palidrom
0
0
Shaikh bro pls tell me that is it always case that LR(1) is only work for dcfl not CFL
0
0

@Prince Sindhiya

question is asking which are wrong, but i read it as which are true.

all the three statements are wrong ===> option a is correct

And why it is not cfg definitely it is cfg

i didn't say as it is not CFG, i said that it is not DCFL, but it is CFL.

 

is it always case that LR(1) is only work for dcfl not CFL

yes... 

0
0
Ok Shaikh brother i got it

Please tell me that that for LL(1) also we require dcfl ?

Becuase what i did ,while giving test i checked all three  ,so from next time first  i will check it that if it is CFL than i will directly reject the option that it will not be parsed LR(1) and LL(1)

I know that every LL(k) is LR(k) and if it is not LR(k) then not LL(k)
0
0

every DCFL has a LR(1) ==> every LR(1) has superset of LL(1).

if it is not DCFL, then how it is LL(1) ?

read the discussion on https://gateoverflow.in/945/gate2003-57

0
0
Yeah i know it just i wanted to confirm thnxx :)
0
0
I hv one more doubt

every LL(1) is LR(1) and in  discussion part it is said that a grammar is LL(1) and not containing ϵ, then it is SLR(1) and so LALR(1) and LR(1).

But i did a question in which it is LL(1) and Lr(1) but not LaLr(1) means the above statement is true only if it is epsilon free LL(1) rit ?
0
0

But i did a question in which it is LL(1) and Lr(1) but not LaLr(1) means the above statement is true only if it is epsilon free LL(1) rit ?

yes

0
0
And one more doubt i am facing for so many days ---- LR(0) generate the DCFL with prefix property (DPDA with empty stack). (Line said by Arjun sir in discussion part )please give me some references so that I can clear this doubt i couldn't understand that what is dpda with empty stack
0
0
0
0

1 Answer

1 vote
1 vote
Best answer

option a is answer

we can make only one parse tree for every  string generated by this grammar , moreover the language generated by this grammar is set of all the even length palindrome

so it is unambiguous 

now it is not LL(1)

because  S ⇒ aSa |  bSb |ε 

here the follow of S is a,b ,$  that is match with the first of right hand side 

it means is row S and column a contain 2 entry  and same thing will happen for column b watch the diagram

  a b $  
S S->aSa,S->epsilon S->bSb,S->epsilon S->epsilon  

now the given grammar is not DCFL  so it is not LR(k)

selected by

2 Comments

Gurdeep Saini I have also followed the same approach for first two but as the given grammar is not DCFL  so it is not LL(k) we can directly say ryt
1
1
edited by

1. Each DCFL can be generated by a corresponding LR(k) grammar and each LR(k) grammar generates one DCFL (one-to-one correspondence). 
2. no DCFL is inherently ambiguous.
3. Each LR(k) grammar is unambiguous grammar, but each unambiguous grammar need not to be LR(k). . 
5. An inherently ambiguous language can only be non-deterministic while an non-deterministic language may or may not be inherently ambiguous.

more about DCFL

1) there are some DCFLs which does not have an LL(k) grammar (see ref below).

2) and for any DCFL, we can always have an LR(K) grammar

http://mathoverflow.net/questions/31733/can-i-have-an-ll-grammar-for-every-deterministic-context-free-language

0
0

Related questions