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.5k 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.