The Gateway to Computer Science Excellence
0 votes
  • 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) | 615 views

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

anyone explain s1 :??

@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 they can be accepted by DPDA na??
one comparison with OR condition makes its cfl. we cannot accept it by DPDA.

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??


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.
this is beacause LR parsers are determinitic ..right??Thankyou

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,737 questions
57,299 answers
104,991 users