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.
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
As , will be composed entirely of ones. Without loss of generality
As , must contain at least one . Without loss of generality
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.
Pingback: Visualizing the Pumping Lemma for Regular Languages - TheBeardSage