1
$\begingroup$

$$L=\{a^{nm} \mid \text{$n$ and $m$ are prime numbers}\}$$

How can i prove $L$ is not context free? I tried pumping lemma but couldn't find an i that $uv^ixy^iz \notin L$.

Any idea or hint on how to prove this?

$\endgroup$
1
$\begingroup$

A simple proof consists to use Parikh's theorem, which states that the commutative image of a context-free language is semilinear. In your case, this theorem implies that if your language is context-free, then the set $$ \{nm \mid \text{$n$ and $m$ are prime numbers} \} $$ is a finite union of arithmetic progressions, or equivalently, that your language is regular. Now, if your language were regular, its intersection with the regular language $(a^2)^*$ would also be regular, that is, the language $$ \{ (a^2)^p \mid \text{$p$ is a prime number} \} $$ would be regular. You should now be able to show that this is not the case.

$\endgroup$
0
$\begingroup$

We want to prove that, for arbitrarily large integers $n$ such that $n$ is the product of two primes, and for all non-negative integers $a,b,c,d, h$ such that $$\begin{cases}a+b+c+d+h=n\\ b+d\ge1\end{cases}$$

there is a positive integer $k$ such that $a+b+c+k(b+d)$ is not the product of two primes.

Since all the info is condensed in $a+b+c=u$ and $b+d=v$, we may just be looking for a $k$ for each $v$ and $u$ such that $u+v=n$ and $v\ge 1$.

Consider three distinct primes $p_1,p_2,p_3$ which do not divide $v$. You want to find $k$ such that $$kv+u\equiv 0\pmod {p_1p_2p_3}$$

Since $v\in \Bbb Z_{p_1p_2p_3}^*$, this is always possible. Explicitly, any positive integer in the form $$k\equiv -u\cdot v^{(p_1-1)(p_2-1)(p_3-1)-1}\pmod {p_1p_2p_3}$$ works. For instance, $k=(p_1^np_2p_3-u)\cdot v^{(p_1-1)(p_2-1)(p_3-1)}$.

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