1 votes 1 votes Theory of Computation context-free-language context-sensitive theory-of-computation + – Payal Rastogi asked Jan 19, 2016 retagged Jul 4, 2017 by Arjun Payal Rastogi 385 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 7 votes 7 votes We can reduce this to $$L = \{0^n1^n0^m \mid n\geq 0, m \leq n\}.$$ We cannot make a PDA for this as we need to do 2 indefinite counts. But we can do this with an LBA and so $L$ is CSL. Answer should be B choice. Arjun answered Jan 19, 2016 selected Jun 23, 2016 by Arjun Arjun comment Share Follow See all 0 reply Please log in or register to add a comment.