23 votes 23 votes The language $\{0^n 1^n 2^n \mid 1 \leq n \leq 10^6\}$ is regular context-free but not regular context-free but its complement is not context-free not context-free Theory of Computation gateit-2005 theory-of-computation easy identify-class-language + – Ishrat Jahan asked Nov 3, 2014 recategorized Nov 6, 2014 by Arjun Ishrat Jahan 6.4k views answer comment Share Follow See all 7 Comments See all 7 7 Comments reply Show 4 previous comments Ankit Kabi commented Oct 17, 2020 reply Follow Share For all n, n=1 L1=012 n=2 L2=001122 . . A FA is possible for L1, L2, ….L10^6. Union of all these FAs will give another FA. Hence regular. 0 votes 0 votes raja11sep commented Jul 19, 2021 reply Follow Share Plz, explain option c. 0 votes 0 votes JAINchiNMay commented Nov 20, 2022 reply Follow Share It says given language is context free and the complement of given language is not context free 0 votes 0 votes Please log in or register to add a comment.
Best answer 32 votes 32 votes Regular (in fact finite). Since $n$ is finite, we have a finite set of strings satisfying the given conditions. So, we can easily make a finite automata for those strings. Arjun answered Nov 13, 2014 edited Feb 21, 2018 by kenzou Arjun comment Share Follow See all 10 Comments See all 10 10 Comments reply Show 7 previous comments Puja Mishra commented Dec 1, 2017 reply Follow Share Yes ..... 0 votes 0 votes ashoka rathore commented Oct 26, 2018 reply Follow Share why not option c is right? language is regular so it is CFL also and complement of CFL is recursive. explain plz? 1 votes 1 votes Pabitra Sahoo commented Jul 31, 2021 reply Follow Share As it is regular, its complement is also regular and hence CFL. so option C is wrong 0 votes 0 votes Please log in or register to add a comment.