1,107 views
3 votes
3 votes

1.Every Ragular Language have an equivalent LR(0)grammer.
2. Every DCFL have an equivalent LR(0) grammer

3 Answers

1 votes
1 votes

Both are False.

Reason is - 

For L = {a, aa} ,  LR(0)  grammar is not possible, Becoz   Look Aheads are 0, whenever we see a, there is a doubt to reduce or to shift. means there will be a shift reduce conflict.

LR(0) form subset of LR(1) , and LR(1) is equivalent to DCFL. so, (2) is False 

https://gateoverflow.in/29489/ll-1-expressive-power

    

edited by
0 votes
0 votes
I think first statement is correct.
1. Every regular language do have an equivalent LR(0) grammar.
2. Every DCFL do not have equivalent LR(0) grammar because DCFL are basically LR(1) and some of LR(1) cannot be converted to LR(0).

So, first statement is correct.

Related questions

0 votes
0 votes
2 answers
1
0 votes
0 votes
1 answer
2
sajalsjddn asked May 29, 2016
867 views
(A) Each one can simulate the other(B) The turing machines always halts which represents all C programs(C) The C programs that always halt can simulate all turing machine...
3 votes
3 votes
2 answers
4
dhruba asked Jun 5, 2023
985 views
In QuickSort algorithm, which of the following statements is NOT true regarding the partition process?a) Partition always divides the array into two non-empty subsets.b) ...