W is a binary representation of a proper power, show that it is not context free with the pumping lemma.

144 Views Asked by At

Here is the full problem description.

I am not sure how to prove that this problem is not context free because I cannot find any "rules" to break. For instance, a problem like "show that w has an equal number of 0's, 1's, and 2's is not context free for w ∈ {0, 1, 2}*" has easily detectable rules (the number of 0's = 1's = 2's).

I don't know how to approach this problem because I cannot seem to find rules for it. 100, 1000, 10000, 1001, 11011, 1010001, 11110011, 100000, are all binary numbers that fit this problem's description but I cannot visualize a pattern/a set of rules that all these binary numbers have in common if that makes any sense.