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.

## Contradiction

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

Pingback: Visualizing the Pumping Lemma for Regular Languages - TheBeardSage