4 votes 4 votes $L = \left \{ a^nb^n \ ; n\geq 0 \ , n \neq 20 \right \}$ is (a) a DCFL (b) a recursive set but not CFL (c) a CFL but not DCFL (d) not a CFL Theory of Computation theory-of-computation closure-property context-free-language + – dd asked Aug 17, 2016 retagged Jul 4, 2017 by Arjun dd 1.2k views answer comment Share Follow See all 21 Comments See all 21 21 Comments reply Show 18 previous comments ManojK commented Aug 18, 2016 reply Follow Share Coming to maching described above logic is somewhat correct but yes dead state is unnecessary used here . @Arjun sir and @Praveen sir pls check PDA described above and make it correct. 1 votes 1 votes dd commented Aug 18, 2016 reply Follow Share And no need to provide transition (x,y,z) in some state , where we are sure that if that particular input(x) and stack(y) combination arise, it's going to be rejected. is it corerct ? @ManojK 0 votes 0 votes ManojK commented Aug 18, 2016 reply Follow Share yes of course . Simple languge a^nb^n |n>1 in which b should not come before a. 1 votes 1 votes Please log in or register to add a comment.
2 votes 2 votes the answer is option (A) DCFL see the link given below for explanation : https://gateoverflow.in/63645/toc?merged=25507 jaiganeshcse94 answered Aug 22, 2016 jaiganeshcse94 comment Share Follow See all 0 reply Please log in or register to add a comment.
–1 votes –1 votes option A it is DFCL because you can make a DPDA how?? you have to take large number of states and reject the n=20 case Shubham Pandey 2 answered Sep 9, 2016 Shubham Pandey 2 comment Share Follow See all 0 reply Please log in or register to add a comment.