# Proving a Language is not Regular using the Pumping Lemma – String Choices

Consider the following language definition



This language is not regular. Applying the pumping lemma to prove that this language is not regular is not straightforward. This is because every string in can be pumped if it has length at least .

## Pump-able Strings

Pick any string with . According the pumping lemma can be written as and for all .

Look at short prefixes of – the symbols that lie at the start of the string. For each of these prefixes, a possible split of into is given below.

All possible prefixes have been taken into account. For all these case, pumping up will add equal number of and substrings. Thus, the string remains in the language.

## Closure under Intersection

Suppose to the contrary is regular. Then is regular by closure under intersection. If is proved to be not regular then the assumption that is regular is wrong. Thus, the problem is reduced to proving that is not regular.

## Using the Pumping Lemma on

Note that the length of every string in is a multiple of .

Let be the pumping length for . Choose .

Then (it has occurrences of and occurrences of ) and , so the pumping lemma applies.

Consider all ways to write with and . Because is a prefix of , it is a prefix of . Thus, is a nonempty substring of .

Write and observe that .

### Case 1

is not a multiple of .

Then . Because is not a multiple of , cannot belong to , which is a contradiction.

### Case 2

is a multiple of .

Say with . Then is one of , , or . For each, has occurrences of and occurrences of , so is not in , a contradiction.

For each case, upon pumping the string goes out of the language. Thus is not regular. This implies that is not regular.