2
$\begingroup$

Parikh's Theorem is quite complicated, I understand intuition of that theorem but I don't see how to use that to prove that language is not context free. I kindly ask you to show me how to do, language isn't important, but for definiteness:

$$ L=\{0^m1^n:m>n\text{ or }(m\text{ is prime and }m\leq n)\}$$

$\endgroup$
3
$\begingroup$

If $L$ were context free, then the set $$ H = \{(m,n) : m > n\} \cup \{(m,n) : m \leq n \text{ and } m \text{ is prime}\} $$ would be semilinear. The set $\{(m,n) : m \leq n\} = \mathbb{N} (1,1) + \mathbb{N} (0,1)$ is also semilinear. The intersection of semilinear sets is also semilinear, so the set $$ H' = \{(m,n) : m \leq n \text{ and } m \text{ is prime}\} $$ is also semilinear. The projection of a semilinear set is semilinear, and so the set of primes is semilinear. But one-dimensional semilinear sets with asymptotic density zero are finite, whereas the set of primes is an infinite set with asymptotic density zero.

$\endgroup$

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.