4 votes 4 votes $L_1=\{(xy)^m(yz)^m\;,\;m\geq 1\}$ $L_2=\{a^mb^nc^k\;|\;m>n\;or\;m<n\}$ Which of the following is True? (a) $L_1$ is CFL, $L_2$ are DCFL (b) $L_1$ is DCFL, $L_2$ is CFL (c) Both $L_1$, $L_2$ are CFLs (d) Both $L_1$, $L_2$ are DCFLS Theory of Computation theory-of-computation identify-class-language + – Rajat Sharma 1 asked Dec 15, 2015 • edited Dec 15, 2015 by Praveen Saini Rajat Sharma 1 1.2k views answer comment Share Follow See all 3 Comments See all 3 3 Comments reply Praveen Saini commented Dec 15, 2015 reply Follow Share But L2 is not DCFL, it is ncfl actually. 0 votes 0 votes Rajat Sharma 1 commented Dec 15, 2015 reply Follow Share But Sir a^nb^m |m>n or m<n is DCFL,and adding c^k will make it NDCFL? 0 votes 0 votes Praveen Saini commented Dec 15, 2015 reply Follow Share Yes, you are right, missed that k is not in condition 0 votes 0 votes Please log in or register to add a comment.
Best answer 9 votes 9 votes Yes $L_2 =\{a^mb^nc^k\;|\;m>n\;or\;m<n\}$ is DCFL having DPDA $L_1=\{(xy)^m(yz)^m\;,\;m\geq 1\}$ is also DCFL having DPDA Praveen Saini answered Dec 15, 2015 • selected Dec 15, 2015 by Rajat Sharma 1 Praveen Saini comment Share Follow See all 4 Comments See all 4 4 Comments reply ankit commented Aug 25, 2016 reply Follow Share Sir , how L2 is DCFL ?? I think it is NDCFL bcoz m>n or m<n 0 votes 0 votes Prashant. commented Aug 25, 2016 reply Follow Share push a and for every a pop b , we have to do it for every language... i think there is no ambiguity na here. so DCFL . 0 votes 0 votes ankit commented Aug 25, 2016 reply Follow Share ok got it sir 0 votes 0 votes hacker16 commented Dec 23, 2017 reply Follow Share I think here m is != n and therefore, it is dcfl. 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes Both are DCFLs L1’s has CFG as follows: S → xySyz | epsilon L2 = { $a^{m}b^{n}c^{k} | m!=n$} Now you can easily think of stack logic. Answer is D reboot answered Dec 26, 2020 reboot comment Share Follow See all 0 reply Please log in or register to add a comment.