0
$\begingroup$

I have the following alphabet $\Sigma = \{0,\dots,9\}$ and the following language over $\Sigma \cup \{\#\}$: $$L=\{\#w \ |\ w \in\Sigma^*,\sum_{i\geq1}w_i\ \text{is prime}\}\\\\$$ This language represents all numbers wich have a prime as digit sum. I now want to show that this language is not context free. I want to show this with a reductio ad absurdum via the pumping lemma and I am not quite sure if I proofed it correctly:

My idea was to just pick a word wich is in $L$ and then show that it cannot be pumped up with the pumping lemma and because if the language is context free every word can be pumped up this shows that $L$ is not context free. But I am not quite sure if this is enough.

Let's assume that L is context free. Then the pumping lemma states that there is a number $k \in \mathbb{N}$ for wich every word $w \in L$ with $|w|\geq k$ can be splitted up like the following $w=xuyvz$ where the following constraints hold:

  • $0<|uv|\leq|uyv|\leq k$
  • $\forall n \in \mathbb{N}:xu^nyv^nz \in L$

Let $k=5$ and $w=\#11111$ because $|w|=6 \Rightarrow |w|\geq k$. We can split up $w$ like this $w=xuyvz$ where the following holds:

  • $x=\#$
  • $u=1$
  • $y=11$
  • $v=1$
  • $z=1$

Because $|uv|=2 \ \land \ |uyv|=4 \Rightarrow 0<|uv|\leq|uyv|\leq k$. Now $\forall n \in \mathbb{N}:xu^nyv^nz \in L$ should also be true. But let $n=3$ then $w'=\#111111111 \notin L$. Thus $L$ is not context free, because the pumping lemma with a number $k \in \mathbb{N}$ is not working for every $w$ with $|w|\geq k$.

I am self learning and have no one who can help me with this, so I really would appreciate if someone could tell me if this proof is working or how I can improve it.

$\endgroup$
2
  • $\begingroup$ It is unclear what "$\sum\limits_{i\geqslant 0}^{10}w_i \text{ is prime}$" means. Does that mean "the sum of the first eleven digits of $w$ is prime"? But it is inconsistent with the following sentence. Please clarify. $\endgroup$
    – Nathaniel
    Jan 9, 2023 at 18:08
  • $\begingroup$ Oh the 10 wasn't supposed to be there. It should mean that the sum of every number is prime. I edited the question. $\endgroup$ Jan 10, 2023 at 13:51

1 Answer 1

1
$\begingroup$

There are several problems in your proof. The language $L$ indeed is not context-free, and the pumping lemma can be used to prove it.

However:

  • you cannot choose the value of $k$ yourself;
  • you cannot choose the values of $x, u, y, v$ and $z$ yourself.

The pumping lemma states that if $L$ is context-free, then THERE EXISTS $k\in \mathbb{N}$ such that FOR ALL $w\in L$ with $|w| \geqslant k$, then THERE EXISTS a decomposition $w=xuyvz$ verifying the three conditions.

However, to prove that $L$ is not context-free, you have to use the contraposition:

If FOR ALL $k\in \mathbb{N}$, THERE EXISTS $w\in L$ with $|w| \geqslant k$ such that FOR ALL decompositions $w=xuyvz$, not all three conditions are verified, then $L$ is not context-free.

The formulation you have seen may be a bit different, but the same ideas are underlying.

Now back to your problem. Let $k\in\mathbb{N}$ be any integer. Consider $p$ any prime number $\geqslant k$. Given the definition of $L$, it is clear that $w = \#1^p\in L$ (here the $^p$ denotes $p$ repetitions, not the mathematical exponentiation).

Suppose $w = xuyvz$ with $|uv| >0$ and $|uyv|\leqslant p$. Let us distinguish:

  • if $uv$ contains the symbol $\#$, then $xyz$ does not contain $\#$ so $xyz\notin L$;
  • that means that $uv = 1^q$ with $0<q\leqslant p$. Then, $xu^{p+1}yv^{p+1}z = xuyvz(uv)^p = \#1^p1^{qp} = \#1^{q(p+1)}$. However, $q(p+1)$ is not prime, so $xu^{p+1}yv^{p+1}z\notin L$.

We conclude that $L$ is not context-free.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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