# Pumping Lemma For Regular Grammars

Contents

## 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 xy
^{k}z 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.**

- Select

**Hence L is not regular.**

### Problem

Prove that **L = {a ^{i}b^{i} | i ≥ 0}** is not regular.

*Solution*

- At first, we assume that
**L**is regular and**n**is the number of states. - Let w = a
^{n}b^{n}. Thus |w| = 2n ≥ n. - By pumping lemma, let w = xyz, where |xy|≤ n.
- Let x = a
^{p}, y = a^{q}, and z = a^{r}b^{n}, where p + q + r = n.p ≠ 0, q ≠ 0, r ≠ 0. Thus |y|≠ 0 - Let k = 2. Then xy
^{2}z = a^{p}a^{2q}a^{r}b^{n}. - Number of
**a**s = (p + 2q + r) = (p + q + r) + q = n + q - Hence, xy
^{2}z = a^{n+q}b^{n}. Since q ≠ 0, xy^{2}z is not of the form a^{n}b^{n}. - Thus, xy
^{2}z is not in L. Hence L is not regular.

## Complement of a DFA

If (Q, ∑, δ, q_{0}, 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.