Prove L = {a^nb^2n } is not regular

Theorem :

Let L be a regular language.

Then there exists a constant ‘c’ such that for every string s in L: |s| ≥ c

We can break w into three strings, s = xyz, such that:

1. |y| > 0

2. |xy| ≤ c

3. For all k ≥ 0, the string   xykz  is also in L.

Method to prove that a language L is not regular:

1. At first, we have to assume that L is regular.

2. So, the pumping lemma should hold for L.

3. Use the pumping lemma to obtain a contradiction:

(a) Select s such that |s| ≥ c

(b) Select y such that |y| ≥ 1

(c) Select x such that |xy| ≤ c

(d) Assign the remaining string to z.

(e) Select k such that the resulting string is not in L.

Proof: L = {anb2n}

Assume L is regular.

From the pumping lemma there exists a p such that every w ∈ L

such that |w| ≥ p can be represented as x y z with |y| ≠ 0 and |xy| ≤ p.

Let us choose apb2p.
Its length is 3p ≥ p.
Since the length of xy cannot exceed p, y must be of the form afor some k > 0.
From the pumping lemma ap-kb2p must also be in Lbut it is not of the right form. Hence the language is not regular

Leave a Reply