Question

Given any string w ∈ {0, 1}∗, let
n0(w) = number of 0′s in w and n1(w) = number of 1′s in w.

Prove, by using the pumping lemma, that the language {w | 0 ≤ n0(w) ≤ 2∗n1(w)+1.}

is not a regular language.

Answer 1

For any regular language L, there exists an integer n, such that for all x ∈ L with |x| ≥ n, there exists u, v, w ∈ Σ∗, such that x = uvw, and
(1) |uv| ≤ n
(2) |v| ≥ 1
(3) for all i ≥ 0: uvⁱw ∈ L

In simple terms, this means that if a string v is ‘pumped’, i.e., if v is inserted any number of times, the resultant string still remains in L.

​​​​​​​