The Gateway to Computer Science Excellence
0 votes
606 views
  •  
  • Which of the following statement/s is/are false for the following language:
    L = {am bn cq | m = n or n = q, m > 0, n > 0, q > 0}
    S1: The language can be parsed by any LR(K) parsers for any value of K.
    S2: The language cannot be recognized by deterministic PDA.
    1.   Only S2
    2.   Only S1
    3.   Both S1 and S2
    4.   Neither S1 nor S2
in Compiler Design by Boss (12.2k points) | 606 views
0

S2: The language cannot be recognized by deterministic PDA (this statement is true)

anyone explain s1 :??

0
@kunal,why the language cannot be accepted by deterministic PDA??can you explain ?is it cuz of OR in the grammar ?but it can be accepted by non-deterministic PDA..right??

but they are separate conditions..so they can be accepted by DPDA na??
0
yes,
one comparison with OR condition makes its cfl. we cannot accept it by DPDA.
0

alright and if it would have been AND then,it could'nt be accepted by cfl also then..right??

and if language is L 1= {am bn cq dp | m = n or p = q, m > 0, n > 0, q > 0,p>0}

and if language is L 2= {am bn cq dp | m = n AND p = q, m > 0, n > 0, q > 0,p>0}

then please tell which is cfl anf which is dcfl??

thankyou

+1
Every LR(K) parser can handle DCFL but as here the language is NCFL ,so we cannot have an LR(K) parser for it. Hence S1 is wrong.
0
this is beacause LR parsers are determinitic ..right??Thankyou
0
Yes.

Please log in or register to answer this question.

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,647 questions
56,508 answers
195,530 comments
100,966 users