Self Doubt in checking whether a language is regular or not

Question

Is there any way to check whether a language is regular or not without using Pumping lemma?

Comments

i agree to u on this :p he is one of my fav. too :P

---

Thank You

---

If a language regular, then it definitely satisfies pumping lemma, but if pumping lemma satisfies, then language may or may not regular

Answer 1

First Just check if it is a finite language or not. Every finite language is regular language.

Now if it's infinite it still can be regular, so check if it compares any two counters. By counter I mean, count of the occurrences of any set of symbols. So if there's even one comparison of counters, it's non regular. Eg a^nb^n

In case there's no comparison between the counter but the counter itself is nonlinear then also the language is non regular. By nonlinear counter, I mean if the languages counts that if number of occurrences of 1 is a prime number, then it will be a non regular language. But if it's prime number from 0 to 1000 then it becomes a regular language because the language will be finite.

These are a few guidelines and the rest can be managed with practice.

Answer 2

1. Check whether the language is finite or not. If its finite then it is surely regular.

2. If its not finite then there may be a case that its not regular.

3. Rules for checking if regular:

a) Check if there is any pattern in AP then its regular.

b) If there is any irregular pattern like in GP or in terms of prime then not regular.

c) If automaton requires saving of infinite length string then comparing then its not regular.

d) Modular counting or modular division is always regular.

4) Pumping Lemma is negativity test means

a) If passed then language may or may not be regular.

b) If failed then language is definitely not regular.