patternMinor
Prove that $\{0^n 1^{n\cdot m} : n,m \in \mathbb{N}\}$ is not context-free
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.
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.
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.