How to prove using pumping lemma {0^n OR 1^2n OR 2^3n | n >= 0} is not context free

This isnt the same language as {0^n1^2n2^3n | n >= 0} as this language the numbers need to be in order.


It is not specified but I'll assume the alphabet to be $\Sigma = \{0,1,2\}$ and also that your strange notation means the language

\begin{align*} L&= \{x \in \Sigma{}^* : x=0^n \lor x=1^{2n} \lor x=2^{3n}, n \in \mathbb{N}\} \\ &=\{0^n : n \in \mathbb{N}\}\cup\{1^{2n} : n \in \mathbb{N}\}\cup\{2^{3n} : n \in \mathbb{N}\} \end{align*}

Well, the answer is that actually it is context-free since each of those three languages is trivially CF and the union of CFLs is also CF.

But it is also Regular! By definition a language is said to be regular if it is accepted by some $DFA$ or, equivalently, if it is expressible by a regular expression.

In our case, $L = 0^*+(11)^*+(222)^*$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.