1 votes 1 votes Theory of Computation theory-of-computation dcfl + – pranab ray asked Dec 9, 2017 pranab ray 713 views answer comment Share Follow See all 10 Comments See all 10 10 Comments reply Anu007 commented Dec 9, 2017 i reshown by Anu007 Dec 9, 2017 reply Follow Share not DCFL 1 votes 1 votes Ashwin Kulkarni commented Dec 9, 2017 reply Follow Share No not DCFL. 0 votes 0 votes Anu007 commented Dec 9, 2017 i edited by Anu007 Dec 9, 2017 reply Follow Share language is L= { 0l 12l 0+ | l >= 0} l+n>=0 we can think, but actual language is L= { 0l 12l 0l 0n| l >= 0} since at last atleast l number of 0 comes.but for L= { 0l 12l 0+ | l >= 0} l+n>=0 we can generate 00110 which is not allow hence atleast 3 comparision 2 votes 2 votes pranab ray commented Dec 9, 2017 reply Follow Share according to my logic it comes DCFL as push number of 0's and then pop 0's by number of 1's ....then remaning 1's are poped by 0's and n numbers of 0's are skipped ....is my logic is right?...given ANSWER it is not DCFL 0 votes 0 votes Ashwin Kulkarni commented Dec 9, 2017 reply Follow Share @Anu007, Yes first I thought same as you, But last 0 should at least same number as initial 0's . I means 0011110 (Is this string accepted?) It should have at least same number as initial 0's then we can increment remaining 0's 0 votes 0 votes Anu007 commented Dec 9, 2017 reply Follow Share now check my comment 0 votes 0 votes Ashwin Kulkarni commented Dec 9, 2017 reply Follow Share Yes now corrected :) 0 votes 0 votes Ashwin Kulkarni commented Dec 9, 2017 reply Follow Share @Pranb check my explanation. You'll get the exact point. Here if you push two 0's for 1's two get 0l12l then how you can verify at least 0l are present in the string or not. hence we required 3 comparisons hence not DCFL 0 votes 0 votes pranab ray commented Dec 9, 2017 reply Follow Share THANKS I GOT IT:) 0 votes 0 votes akshat sharma commented Dec 9, 2017 reply Follow Share if in last 0 it is 0^n then we can say that it is DCFL 0l12l0n 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes This language is not even a CFL. Apply pumping lemma on $0^{n}1^{2n}0^{n}$ Joey answered Dec 12, 2022 Joey comment Share Follow See all 0 reply Please log in or register to add a comment.