Question

1. Prove that {anbamba2m+n:n,m≥1} is not regular using pumping lemma (5).

Answer 1

solution:

pumping leema for regular language:

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 given language is regular.

X = ababaaa

n=5

So, |×| > = n

u= aba

v= ba

w= aa

First condition : |uv| <= n it satisfied.

Because | ababa| <= 5

Second condition:| v| >= 1 it satisfied

Third condition: uv^iw

Let, i=2

V = (ba)^2

uv^2w = abababaaa does not belong to L.

So third condition does not satisfied.

so L is not regular hence proof.

please give e thumb up