The Gateway to Computer Science Excellence

+4 votes

Which of the following statements is FALSE?

- Any DCFL has an equivalent grammar that can be parsed by a SLR(1) parser with end string delimiter
- Languages of grammars parsed by LR(2) parsers is a strict super set of the languages of grammars parsed by LR(1) parsers
- Languages of grammars parsed by LL(2) parsers is a strict super set of the languages of grammars parsed by LL(1) parsers
- There is no DCFL which is not having a grammar that can be parsed by a LR(1) parser

0

@Arjun Sir, is the answer C?

my reasoning is as follows,

consider a grammar

S -> aA/aB

A -> cA/c

B -> bB/b

The above grammar is LL(2).

now the above grammar can be converted into LL(1) as follows

S -> aS'

S' -> cA/ϵ

S' -> bB/ϵ

similarly every other LL(2) grammar should be convertable to LL(1) grammar.

0

@Arjun Option A holds for both SLR(1) and LR(0) then?

https://gatecse.in/category/compiler-design/

Sir, here it is mentioned that

Language of LR(0) (set of all LR(0) grammars) is same as "DCFL having prefix property"

Then how can Option A hold true for LR(0)?

0

Reffering from the diagram in... https://gateoverflow.in/1470/gate1999-1-17#16773

Iam confused how B is false. @Arjun sir please help. which one of them is true.

0 votes

Answer is B

LR(0) ⊂ LR(1) = LR(2) ........LR(k) = LR(k+1) ; for k >= 1 : LR(k)=LR(k+1)

so, Languages of grammars parsed by LR(2) parsers is not a strict super set of the languages of grammars parsed by LR(1) parsers

although they both are same ;

if you compare their grammars :

LR(0) ⊂ LR(1) ⊂ LR(2) ........LR(k) ⊂ LR(k+1)

LR(0) ⊂ LR(1) = LR(2) ........LR(k) = LR(k+1) ; for k >= 1 : LR(k)=LR(k+1)

so, Languages of grammars parsed by LR(2) parsers is not a strict super set of the languages of grammars parsed by LR(1) parsers

although they both are same ;

if you compare their grammars :

LR(0) ⊂ LR(1) ⊂ LR(2) ........LR(k) ⊂ LR(k+1)

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,309 answers

198,336 comments

105,022 users