# Pumping Lemma For Regular Grammars

Posted By on April 29, 2016

## Pumping Lemma for Regular Languages

### Theorem

Let L be a regular language. Then there exists a constant ‘c’ such that for every string w in L

|w| ≥ c

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

• |y| > 0
• |xy| ≤ c
• For all k ≥ 0, the string xykz is also in L.

### Applications of Pumping Lemma

Pumping Lemma is to be applied to show that certain languages are not regular. It should never be used to show a language is regular.

• If L is regular, it satisfies Pumping Lemma.
• If L is non-regular, it does not satisfy Pumping Lemma.

### Method to prove that a language L is not regular

• At first, we have to assume that L is regular.
• So, the pumping lemma should hold for L.
• Use the pumping lemma to obtain a contradiction −
• Select w such that |w| ≥ c
• Select y such that |y| ≥ 1
• Select x such that |xy| ≤ c
• Assign the remaining string to z.
• Select k such that the resulting string is not in L.

Hence L is not regular.

### Problem

Prove that L = {aibi | i ≥ 0} is not regular.

Solution

• At first, we assume that L is regular and n is the number of states.
• Let w = anbn. Thus |w| = 2n ≥ n.
• By pumping lemma, let w = xyz, where |xy|≤ n.
• Let x = ap, y = aq, and z = arbn, where p + q + r = n.p ≠ 0, q ≠ 0, r ≠ 0. Thus |y|≠ 0
• Let k = 2. Then xy2z = apa2qarbn.
• Number of as = (p + 2q + r) = (p + q + r) + q = n + q
• Hence, xy2z = an+q bn. Since q ≠ 0, xy2z is not of the form anbn.
• Thus, xy2z is not in L. Hence L is not regular.

## Complement of a DFA

If (Q, ∑, δ, q0, F) be a DFA that accepts a language L, then the complement of the DFA can be obtained by swapping its accepting states with its non-accepting states and vice versa.

We will take an example and elaborate this below −

This DFA accepts the language

L = {a, aa, aaa , …………. }

over the alphabet

∑ = {a, b}

So, RE = a+.

Now we will swap its accepting states with its non-accepting states and vice versa and will get the following −

This DFA accepts the language

Ľ = { ε , b, ab ,bb,ba, …………… }

over the alphabet

∑ = {a, b}

Note − If we want to complement an NFA, we have to first convert it to DFA and then have to swap states as in the previous method.

#### Posted by Akash Kurup

Founder and C.E.O, World4Engineers Educationist and Entrepreneur by passion. Orator and blogger by hobby

Website: http://world4engineers.com