26 votes 26 votes The language $L=\left\{0^i21^i \mid i \geq 0\right\}$ over the alphabet $\left\{0, 1, 2\right\}$ is: not recursive is recursive and is a deterministic CFL is a regular language is not a deterministic CFL but a CFL Theory of Computation gatecse-2007 theory-of-computation normal identify-class-language + – Kathleen asked Sep 21, 2014 Kathleen 8.5k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 40 votes 40 votes $L=\left\{0^i21^i \mid i \geq 0\right\}$ has only one comparison that can be done using a DPDA. Hence, its DCFL. Context free languages are a proper subset of Recursive Languages. $\therefore$ it is recursive too. Answer is option B. amarVashishth answered Nov 15, 2015 • edited Jun 15, 2018 by Milicevic3306 amarVashishth comment Share Follow See all 2 Comments See all 2 2 Comments reply CSHuB commented Jan 31, 2020 reply Follow Share We can draw DFA as well? as the state "2$ will help? Isn't it?? –1 votes –1 votes Pranavpurkar commented Oct 31, 2022 reply Follow Share CSHuB $DFA$ not possible. 0 votes 0 votes Please log in or register to add a comment.
19 votes 19 votes L = {0i21i | i>=0 } is deterministic CFL, Evert DCFL is recursive. As we have membership algorithm for DCFL (Or say CFL in general) , that's why it is recursive. In fact DCFL is subset of Recursive Languages. SO answer :- B Akash Kanase answered Nov 14, 2015 Akash Kanase comment Share Follow See all 3 Comments See all 3 3 Comments reply Raju Kalagoni commented Mar 6, 2018 reply Follow Share How to find DCFL and CFL ? can you please explain the difference between these two and how to identify them ? 0 votes 0 votes meghna commented May 10, 2018 reply Follow Share Identification of whether DCFL or CFL? The very basic thing to look out first, is whether you can generate that language using a PDA or not ? Relate it with stack and just by using push and pop can you generate it ? If so, its a CFL. Now if the PDA that you are using, is deterministic at each step, that is you are clear about the next move every single time, then it's a DCFL, otherwise if there is any non determinism involved, that is there are some steps where more than one move is possible, and you are not certain about the action, then its CFL. While remembering the fact that DCFL is a proper subset of CFL. Ex: let L= {anbn}, it is CFL because, with the help of PDA (push down automata), we can recognize it. We have n a's followed by n b's. we can push all a and corresponding to each b, we can pop a. if they are equal stack will be empty. if a are more, stack will have a. if stack becomes empty before finishing string, it means we have more b. It is DCFL as well because, we know we have to push a and pop for b, the action is deterministic. On the other hand, {wwR, where w is a string of a and b} is non deteministic CFL because till half of the length, we have to push and then we have to pop. but we dont know length. So at each step, we will push the next symbol and pop the previous one to see which one works. so it is non deteminsitic. So a CFL will be either deterministic or non deterministic. 20 votes 20 votes Pranavpurkar commented Oct 31, 2022 reply Follow Share @meghna Perfectly explained. 0 votes 0 votes Please log in or register to add a comment.
6 votes 6 votes push all 0 then skip 2 then for every 1 pop one 0 .. done by 1 stack without any confusion.. so dcfl. dcfl⊆ cfl ⊆ csl ⊆ rec ⊆re Prashant. answered Nov 15, 2015 Prashant. comment Share Follow See all 3 Comments See all 3 3 Comments reply Puja Mishra commented Jan 1, 2017 reply Follow Share transition for skip ??? i am getting little bit confused there .... 0 votes 0 votes Sandeep Suri commented Jan 10, 2018 reply Follow Share yes when 2 will come we don't need to perform any operation, therefore, we will bypass (skip) 2 and then perform a pop operation on seeing 1 0 votes 0 votes Subbu. commented Oct 29, 2021 reply Follow Share It should be proper subset.. 0 votes 0 votes Please log in or register to add a comment.
2 votes 2 votes The answer is B. Gate Keeda answered Jan 22, 2015 Gate Keeda comment Share Follow See all 0 reply Please log in or register to add a comment.