Question

Prove the following languages are not context-free by using the pumping
lemma.

{b(n) #6(n + 1) | n є N, n-1} where b(n) is binary representation of n with no leading 0

Answer 1

Pumping Lemma for CFL states that for any Context Free Language L, it is possible to find two substrings that can be ‘pumped’ any number of times and still be in the same language. For any language L, we break its strings into five parts and pump second and fourth substring.
Pumping Lemma, here also, is used as a tool to prove that a language is not CFL. Because, if any one string does not satisfy its conditions, then the language is not CFL.
Thus, if L is a CFL, there exists an integer n, such that for all x ∈ L with |x| ≥ n, there exists u, v, w, x, y ∈ Σ∗, such that x = uvwxy, and
(1) |vwx| ≤ n
(2) |vx| ≥ 1
(3) for all i ≥ 0: uvⁱwxⁱy ∈ L

Let us assume that n = 8.

Then, b(n) = 1000 and b(n+1) = 1001

Hence, x = 1000#1001

Let

u = 1000#, v = 1, w = 0, x = 0 and y = 1

Clearly, |vwx| ≤ n and |vx| ≥ 1

And, uvⁱwxⁱy = 1000#1ⁱ00ⁱ1

Clearly, 1ⁱ00ⁱ1 does not represent b(n+1) and hence, L is not context free.