Skip to content

Showing balanced parens to be irregular

September 26, 2013

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:
L_{()} = \{ (^n \varphi )^n | n \geq 1 \wedge \varphi \neq \Lambda \} is not a regular language.
Method:
Some text books use \Lambda to denote the empty string so here \varphi 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), \exists m so that m can be used to split w \in L_{()} into parts. We actually use this m to form w. We can do this because the Lemma says this m is valid for any w, |w| \geq m.
Proof:
Assume L_{()} to be regular. Then by PLem,  there exists an m such that for w \in L_{()}, |w| \geq m. Consider now the w formed by setting n = m. Then we have w = (^m \varphi )^m. Further we know that |w| = 2m+1 > m satisfying PLem premise, so it can be applied. As per PLem,  we can break w into x, y, z components. As per PLem also |xy| \leq m. Looking at the form of our w this implies that xy must be composed of all left parenthesis, i.e  xy = (^m, then y=(^p for some p < m.  As per PLem, we can pump y  for any k \geq 0.  So let k =0 then the new w = (^{m-p} \varphi )^m. But this implies that |(^{m - p}| = m - p \neq m =|)^m|, i.e. parentheses are not balanced. But this means w \not \in L_{()}. Contradiction. At this point we have found a k where the decomposition results in the string outside of L_{()}and we can stop.

Anyway consider now also y pumped upwards to k. Then we have the new w = (^{m-p}(^{pk} \varphi )^m. Looking at the left of \varphi we have |(^{m-p}(^{pk}|= m - p + pk \neq m= |)^m|. Again the parentheses do not balance out. Thus w \not \in L_{()}. Contradiction.

Q.E.D.

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

Advertisements
No comments yet

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: