Question

In the class, we have shown that L {a"bn·n > 0} is not regular. Use the pumping lemma to show that Ls -[a"b*c: n 2 0, k 2 n] is not regular. Can you prove by a simpler way using homomorphism? nhn.

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.

Let us assume that u = aⁿb^k, v = a^p, w = a^n-p

Clearly,

|uv| ≤ n and |v| ≥ 1

Now, uvⁱw = aⁿb^ka^ipa^n-p = aⁿb^ka^n+(i-1)p

Clearly, for larger i, we cannot guarantee that k >= n+(i-1)p

Therefore, L is not regular.