# Showing balanced parens to be irregular

This is for young people doing CS and are wondering how to use the Pumping Lemma to verify if a formal language is regular or not :-). So let us have a theorem about the balanced parenthesis language :

**Theorem**:

is not a regular language.

**Method**:

Some text books use to denote the empty string so here is none empty. The method of proof is by contraction (Reduction ad Absurdium – RAA). So we assume the language is regular and hence can be pumped but show it to be otherwise, or not true by arriving at a contradiction. By the Pumping Lemma (PLem), so that can be used to split into parts. We actually use this to form . We can do this because the Lemma says this is valid for any .

**Proof**:

Assume to be regular. Then by PLem, there exists an such that for , . Consider now the formed by setting . Then we have . Further we know that satisfying PLem premise, so it can be applied. As per PLem, we can break into components. As per PLem also . Looking at the form of our this implies that must be composed of all left parenthesis, i.e , then for some . As per PLem, we can pump for any . So let then the new . But this implies that , i.e. parentheses are not balanced. But this means . Contradiction. At this point we have found a where the decomposition results in the string outside of and we can stop.

Anyway consider now also pumped upwards to . Then we have the new . Looking at the left of we have . Again the parentheses do not balance out. Thus . Contradiction.

Q.E.D.

Feedback is appreciated – let me know if it has helped/not helped. Thanks.