How to check whether a language is regular or not?

Question

Say I have a given expression like $L_1\{a^n\mid n\ge0\}$ $L_2\{b^n\mid n\ge 0\}$ Then what is the procedure of checking weather L1.L2 is regular or not?

Answer 1

Firstly, I will tell you how to check whether a given language is regular or not.

As there are no specific algorithms to do that,it comes by practice and experience.

But the given flowchart can make your life easier for tackling this type of problems:

Flow Chart For Checking Whether A Given Language Is Regular or Not

Now according to the flowchart, you can see that the language L1 and L2 are not finite because there is no upper bound on $n$, but it doesn't implies that the language is not regular, you need to further check whether memory is required by the given language or not, so for the language L1 and L2, memory is not required. So if memory is not required, you need to find some pattern in the language such you can use that pattern in designing the Finite Automata (FA).

So, in both the languages L1 and L2 the length of the string is in AP.

For L1; $$ a^n,n>=0 $$ $ a^0,a^1,a^2,.....,a^n$ forms an AP in terms of the length of the string. Same case for L2 (just replace $a$ by $b$).

As there is a pattern in the language L1 and L2, we can write the regular expressions for L1 and L2:

Regular Expression for $ L1=a^*$ and for $L2=b^*$.

**If we are able to write a regualr expression for the given language then we can design the FA.

Therfore the two languages L1 & L2 are both regular language because you can write a regular expression for them which implies you can design the finite automata to accept the strings generated by the language.

Now, your question is what if we concatenate (L1.L2) the strings generated by L1 with strings generated by L2 means strings generated by L2 must follow string generated by L1.

$$L=\{a^nb^n | n>=0\}$$ Eg. of the strings generated by this language is :$$\epsilon,ab,aabb,aaabbb,...$$ You can see from the example that number of b's $=$ number of a's and b's must follow a's.

You cannot design a regular expression and FA for this langauge because you need extra memory to check whether the number of b's $=$ number of a's or not, and the memory which you required is a stack.

For E.g, Suppose you want to check whether $aabb$ belongs to L or not.

What you will do is,you push all the $a's$ into the stack and for every $b$ you encounter,you will pop out an $a$ from the stack. At the end of the string if the stack is empty means,

number of $a's$ $=$ number of $b's$ $=>$ string will be accpeted by the given language L.

**For your knowledge, this language L=L1.L2 is an example of context free language and the automata needed for context free language is known as a Push Down Automata=Finite Automata + 1 stack.