a^nb^n is the regular such that n>=0

bogosort

Joined Sep 24, 2011
696
In slide 13/15 they have shown that a^nb^n is not regular when n>=0.

However I can’t understand the last slide where they show that there is a contradiction.
The proof uses the pumping lemma, which basically says that a string in some regular language L can be lengthened by repeating symbols, and that this new string is also in L. For example, a word 'xyz' -- where 'x', 'y', and 'z' are sequences of symbols from the language's alphabet -- can be expanded to 'xyyz' by repeating the 'y' group of symbols. The pumping lemma provides the precise mathematical details for how this can be done.

Now, the words in the language L = { (a^n)(b^n) } are strings such as "ab", "aabb", "aaabbb", etc. We assume that this language is regular. The pumping lemma can be used to show that if L is regular and some string 'xyz' is in L, then 'xyyz' must also be in L. But if you work out what 'xyz' means in the language (a^n)(b^n), you'll find that 'xyyz' represents a word in [a^(m+k)][b^m], with k > 0, which is clearly not in (a^n)(b^n). Since this is a contradiction -- i.e., 'xyyz' is supposed to be in L, but it's not -- then our assumption that L is regular must be false.

This video does a good job of explaining the machinery of the proof:
 

WBahn

Joined Mar 31, 2012
29,979
Hi,
I have got following link:

https://www.cs.colostate.edu/~massey/Teaching/cs301/RestrictedAccess/Slides/301lecture06.pdf

In slide 13/15 they have shown that a^nb^n is not regular when n>=0.

However I can’t understand the last slide where they show that there is a contradiction.

I have attached the first and last slides.
The contradiction comes about because of the work in all of the slides that you didn't show. They can't be ignored.

The Pumping Lemma for Regular Languages is an observation regarding a property that all regular languages have (though it does not preclude non-regular languages from having that same property). Thus, satisfying the Pumping Lemma is a necessary condition for a language to be regular, however it is not a sufficient condition. This is an important point that is lost on many, many students.

I liken this to the Egg Laying Lemma For Birds, which states that all birds reproduce by laying eggs. While having this property is a necessary condition for a species to be a bird, it is not a sufficient condition since it does not preclude non-bird species from laying eggs. So, if you show me a species and I can prove that it reproduces by some means other than laying eggs, I have proven that it is not a bird. But if I prove that it does reproduce by laying eggs, I have not proven that it is a bird -- it could be a crocodile.

Other common misconceptions include that every string in a regular language is pumpable. This is NOT what the Pumping Lemma states. Is states that every string in a regular language that is at least as long as a pumping length for that language is pumpable. Strings that are shorter than the minimum pumping length may or may not be pumpable.

Yet another common misconception is that every partitioning of every pumpable string is pumpable. This is NOT what the Pumping Lemma states. It states that for every string that is at least as long as a pumping length for that language, that there exists at least one pumpable partitioning of that string. In order to show that the string is not pumpable, you must show that no such partitioning exists, which means that you have to structure your proof such that every conceivable way of partitioning the string is covered and shown to be nonpumpable.

Because the Pumping Lemma for Regular Languages can only be used for showing that a particular language is not regular, the normal means of doing so is by counter example, which is normally formalized as a proof by contradiction. We assume that the language is regular and construct a string that is both in the language and at least as long as a pumping length. We then show that every possible way of partitioning that string results in a nonpumpable string. Since the Pumping Lemma requires that every such string be pumpable, by showing a counter example of such a string that is not pumpable, we have a contradiction meaning that at least one of our assumptions is false. Since the only assumption we made was that the language was regular, that assumption must be the one that is incorrect and, in actuality, the language is not regular.
 

Thread Starter

zulfi100

Joined Jun 7, 2012
656
The proof uses the pumping lemma, which basically says that a string in some regular language L can be lengthened by repeating symbols, and that this new string is also in L. For example, a word 'xyz' -- where 'x', 'y', and 'z' are sequences of symbols from the language's alphabet -- can be expanded to 'xyyz' by repeating the 'y' group of symbols. The pumping lemma provides the precise mathematical details for how this can be done.

Now, the words in the language L = { (a^n)(b^n) } are strings such as "ab", "aabb", "aaabbb", etc. We assume that this language is regular. The pumping lemma can be used to show that if L is regular and some string 'xyz' is in L, then 'xyyz' must also be in L. But if you work out what 'xyz' means in the language (a^n)(b^n), you'll find that 'xyyz' represents a word in [a^(m+k)][b^m], with k > 0, which is clearly not in (a^n)(b^n). Since this is a contradiction -- i.e., 'xyyz' is supposed to be in L, but it's not -- then our assumption that L is regular must be false.

This video does a good job of explaining the machinery of the proof:
The proof uses the pumping lemma, which basically says that a string in some regular language L can be lengthened by repeating symbols, and that this new string is also in L. For example, a word 'xyz' -- where 'x', 'y', and 'z' are sequences of symbols from the language's alphabet -- can be expanded to 'xyyz' by repeating the 'y' group of symbols. The pumping lemma provides the precise mathematical details for how this can be done.

Now, the words in the language L = { (a^n)(b^n) } are strings such as "ab", "aabb", "aaabbb", etc. We assume that this language is regular. The pumping lemma can be used to show that if L is regular and some string 'xyz' is in L, then 'xyyz' must also be in L. But if you work out what 'xyz' means in the language (a^n)(b^n), you'll find that 'xyyz' represents a word in [a^(m+k)][b^m], with k > 0, which is clearly not in (a^n)(b^n). Since this is a contradiction -- i.e., 'xyyz' is supposed to be in L, but it's not -- then our assumption that L is regular must be false.

This video does a good job of explaining the machinery of the proof:
Hi bogosort,
Thanks for your reply. You mean its not regular because we have following case:
[a^(m+k)][b^m]

if its [a^m][b^m], it would be regular. This means that the string is not pumpable as said by WBahn. Thanks a lot.

God bless you.

Zulfi.
 

WBahn

Joined Mar 31, 2012
29,979
I just looked through the slides you linked and their proof is pretty sloppy -- so much so that it isn't really valid, although the gist is certainly correct.

On the first slide of page 14 they claim that y = a^k for k >= 1. This allows k to be greater than m, but since there are only m a's in the original string this is not possible. Their constraint should be

y = a^k for some k such that 1 <= k <= m

That 'for some k' is pretty important (but not critical if left out) because it is important that we keep in mind that what we have really done is said every possible partition of interest can be written in the form such that y consists of some nonzero string of a's.

They got sloppy and forgot that point when they made their conclusion that a^(m+k)b^(m) must be in L if L is regular because they still only constrain L to be a strictly positive integer. But that is not what the Pumping Lemma is requiring, it is requiring only that there must exist some specific k between 1 and m (inclusive) for which this must be true, not every k. But this is sufficient to show the necessary contradiction.

Here's one for you to practice with that is similar to this one but requires a slight twist.

Show that L = {a^m b^n | m >= n} is not regular.
 

bogosort

Joined Sep 24, 2011
696
There are 10 types of people in the world: those who understand binary, those who don't, and those who can work in any number base.
Completely off-topic, but I'm very pleased to see your version of this trope. I'm excessively (irrationally?) bothered by the versions that are restricted to the base-2 case.
 

WBahn

Joined Mar 31, 2012
29,979
Completely off-topic, but I'm very pleased to see your version of this trope. I'm excessively (irrationally?) bothered by the versions that are restricted to the base-2 case.
I wish I could claim I came up with it, but I didn't. Saw it on a tee shirt a decade or two ago and every time I see the base-2 version I immediately think of the general case.

When I teach number representation I will throw out the question of why, when we indicate the number base in use, we always represent it in base-10 and not in the number base in use. Very rarely do I get someone that is able to think it through far enough to spot the problem with doing so.
 
Top