HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Prove that $\{0^n 1^{n\cdot m} : n,m \in \mathbb{N}\}$ is not context-free

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
mathbbfreeprovecdotthatcontextnot

Problem

This is a homework problem I have spent several hours on. A "hint" is given that we may use this fact: If $n,j,k \in \mathbb{N}$ satisfy $ n \geq 2$ and $1 \leq j+k \leq n$, then $n^2+j$ does not evenly divide $n^3+k$.

I cannot find any way to apply this fact. It leads me to believe I should use the string $0^{p^2}1^{p^3}$ or something like that, but I am really just not sure. The pumping lemma has given me trouble since the non regular language version.

Even small hints greatly appreciated at this point.

Solution

If you use the pumping lemma on the word $w=0^{p^2} 1^{p^3}$, consider the partition $w=xyzuv$, where $|yzu|\le n$ and $|yu|>0$ ($n$ being the length of $w$).
It is easy to prove that from all the cases (that is, from all the possibilities for $y$ and $u$), the only non-trivial case is when $y=0^i$ and $u=1^j$, in which case the hint you mentioned finishes the job.

Context

StackExchange Computer Science Q#9808, answer score: 5

Revisions (0)

No revisions yet.