how to find whether a language is regular or not

Question

my question is whether we have a shortcut an idea which can help us in recognizing any language to be regular or not,in GATE .and also what is the best way to get it properly done when you want to do it the old school way?

Comments

If Language is Finite..It has to be Regular as You can draw DFA easily..

If Language is Infinite Then it may be Regular or Non Regular..

In Case your lang is infinite then try to check:

1) Is there any matching of some alphabets? Yes then Non Regular

2)   Counting is being done? Yes then Non-Rgular.

3) When Language Requires Memory requires to maintain a count...then such Language is non-regular.

4) If Power is in non-linear Relationship then also it is non-regular..

Answer 1

Check following thing .

1. Is DFA/NFA or regular expressions possible or not (especially in case of WW, WWr, W1W2.....)

2. String matching ---> non regular

3. Counting comparison ---> non regular

4. Power is non linear ---> non regular

5. If finite then regular.. it doesn't matter comparison or string matching or power is non linear if language is finite it must be regular.. even finite subset of non regular is regular..

Still some more but questions base on these 5 points frequently asked in GATE..

referhrefer : http://gatecse.in/wiki/Identify_the_class_of_the_language

Comments

This might also help:

http://gatecse.in/wiki/Identify_the_class_of_the_language

---

But sir, then how can a language requires having a greater than or equal to b is regular as it requires memory and also counting of a's and b's

---

What is that language?

---

Sorry sir I got it. I confused with (a,b)* with sigma*