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