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