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 lU$er commented Dec 21, 2016 reply Follow Share This language is regular, then it must also be a CFL. I was wondering what would be the logic for the PDA? Can you give some hints? 1 votes 1 votes Sachin Mittal 1 commented Dec 27, 2016 reply Follow Share @Anirban Roy , Just dont use stack. 4 votes 4 votes KISHALAY DAS commented Jan 3, 2017 reply Follow Share Yes i think just having state transition we can do it in pda...right sachin?? 2 votes 2 votes Sachin Mittal 1 commented Jan 3, 2017 reply Follow Share Yes, Right. 4 votes 4 votes sumit chakraborty commented Dec 1, 2017 reply Follow Share Hey @Arjun I was just thinking we still have to count the number of 0 and number of 1 and number of 2 to be equal. I get your answer about finite and hence regular but how will the counting take place in the state transition diagram for all strings generated by the language. 1 votes 1 votes Puja Mishra commented Dec 1, 2017 reply Follow Share its an regular language union ... make dfa for individual n then union it ...same logic for pda ... as CFL and regular language is closed under union .. 5 votes 5 votes sumit chakraborty commented Dec 1, 2017 reply Follow Share So for a language anbncn if n is a finite number (however big the number is) the language is regular but if n is undefined or is infinite then the language is a CSL ? 4 votes 4 votes 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.