search
Log In
0 votes
805 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 805 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.

Related questions

0 votes
1 answer
1
4k views
(A) Context-free languages are closed under union. (B) Context-free languages are closed under concatenation. (C) Context-free languages are closed under intersection. (D) Context-free languages are closed under Kleene closure.
asked May 26, 2016 in Theory of Computation im.raj 4k views
0 votes
3 answers
2
344 views
Q16). Let $f(x)$,$g(x)$ and $h(x)$ be functions which of the following statement is false? a). if $f(x)$ is $O(g(x))$ and $g(x)$ is $O(h(x))$ then $f(x)$ is $O(h(x))$. b). if $f(x)$ is $\Omega(g(x))$ and $f(x)$ is $\Omega(h(x))$ ... and $(b)$ d). Neither $(a)$ nor $(b)$ I mean according to me , option (a) is correct , right ? by the rule of transitivity . Please correct me , if I am wrong.
asked Jan 18, 2016 in Algorithms worst_engineer 344 views
5 votes
1 answer
4
524 views
Which of the following is not a recursive language? a. Regular language b. {$\langle M,w \rangle$ | $M$ is a DFA that accepts $w$} c. {$\langle M \rangle$ | $M$ is a TM and there exists an input which halts within $100$ steps} d. {$\langle M \rangle$ | $M$ is a TM and $L(M)$ is regular }
asked Sep 11, 2015 in Theory of Computation Shefali 524 views
...