# Proving a Language is not Regular using the Pumping Lemma

Consider the following language definition



This language is not regular. This article explores a step by step approach to prove this by contradicting the Pumping Lemma for Regular languages.

## Assumption

Suppose to the contrary is regular and be its pumping length. Let and denote the number of and substrings in respectively.

## Choosing a string

A string has to be chosen such that it satisfies the following two conditions



Consider the string .



## Stating the Pumping Lemma

According to the Pumping Lemma for Regular languages, can be written as , satisfying the following conditions



## Case 1:

As , will be composed entirely of ones. Without loss of generality



## Case 2:

As , must contain at least one . Without loss of generality



## Case 3:



For to hold true



This will hold true , if . But according to Case 2, . This is a contradiction and all possible cases of expressing have been considered.

The Pumping Lemma does not hold true. This means the assumption that is Regular was wrong. Thus, is not Regular.