# What is not a regular expression

I see that a lot of people are still facing confusion regarding regular expression. So I am going to explain that with some examples in this text. It will be a long text but read it.

1)a^m b^2m where m>=0.

This expression is not a regular expression. Why?

Well , you can see that m is unbounded here. So, the language this expression generates is an infinite language. Right? Now, if we see some of the strings in this language, they are abb,aabbbb,aaabbbbbb,…. . If you notice, you will see that in these strings, there are some a’s at first then the sequence of a is followed by b and the number of b’s is twice of the number of a’s. Now, for this, when we write b, we need to remember how many a’s we had to ensure that the number of b’s is twice of a. Right? That means we need memory to remember the amount of a. However, the machines we use to represent regular language do not have any memory. They can not remember their previous states. As they can not remember, they can not ensure that the number of b is twice of the number of a. So, we can not represent this language with the machines we use for regular language. Thus, this language is not a regular language. As the language is not regular, it can not be expressed with regular expression. So, the expression is not regular.

2) a^n b^m where n,m>=0.

This is a regular expression. Why?

Well, you see that the strings that can be generated from this expression will have some number of a’s at first and then followed by some number of b’s. Here we do not need to remember anything. As we do not need to remember anything, the language can be represented by the machines we use for regular languages. So, the language will be regular and thus the expression will also be regular.

3) a^n b^n where n <1000.

This is a regular expression but why?

At first, see that n is bounded here. As, n is bounded, the language will be finite. Maybe the set of the strings of this language can be very very big but the important thing is that the set is finite. So, this language is a finite language and every finite language is a regular language. So, the expression will be regular too. Now let’s explain why it will be regular.

Let’s consider that n<4 and n>=0 for simplicity. So, the language will be { ε, ab,aabb,aaabbb}. Now, we know that our machine can not remember but see that now we know the exact strings that are accepted. So, what we can do is we can create separate machines for each strings and then merge it together in parallel. By this way, we can ensure that only these strings will be accepted by our machines with no memory required. So this will be regular language as we are now being able to express. So, it will be regular expression.

Now, let us consider our main example where n<1000. Here, the set of the language will be very very big but the important thing is that the set is finite. As, it is finite, we will be able to count how many elements there are and what are the elements. So, we will be able to build separate machines for each of them and merge them together in parallel. So, this language can be expressed with the machine of regular languages so it will be a regular language. Thus, the expression will be regular.

Example-3: