snippetMinor
How to use Parikh's Theorem to show language is not context free
Viewed 0 times
showfreeparikhlanguagetheoremhowcontextusenot
Problem
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)\}$$
$$ L=\{0^m1^n:m>n\text{ or }(m\text{ is prime and }m\leq n)\}$$
Solution
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.
$$ 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.
Context
StackExchange Computer Science Q#57471, answer score: 4
Revisions (0)
No revisions yet.