# How to guess whether a language is regular or not

I have a few languages and I am not given whether they are regular or not. If I had to prove their irregularity, then it would not have been difficult. How do I go about finding if the language is regular/irregular and then justifying my answer.

-
Remember that it is polite to vote up answers you like and accept answers you like the most! This will make it more likely that people will help you in the future :) –  sxd Jun 16 '12 at 23:59
The language is regular if and only if you can decide whether a word belongs to it with keeping only constant amount of information, e.g. constant number of bytes. Please note, that constant memory is not enough to hold one natural number of any size, but it will suffice if it is bounded by a constant. –  dtldarek Jun 17 '12 at 7:56
There is a similar question on cs.SE. –  Raphael Jun 17 '12 at 16:25

What I do is the following:

If I suspect that it is a regular language (usually by checking whether you need to save some information or whether you have to be able count):

• First I check whether I can easily come up with a DFA / NFA.

• If that does not work, I check whether it is the union/intersection/... of languages that are pritty well known to be regular. (Remember regular languages are closed under union etc)

If I suspect that it is irregular (usually this happens when the language does require counting, or 'saving' data. Or I compare them to a list of well known irregular languages, and check whether they are alike):

• First, I check if I can write the language $L$, as $A \cup L = C$, where A is regular and $C$ is irregular, then $L$ can't be regular! This method works for any operation regular languages are closed under.

• If that does not work, then I check if it is easy to use the pumping lemma.

-
Example. Consider a finite set of strings such as $\{ \text{cat}, \text{dog} \}$. Can I check whether a huge string doesn't contain any of these strings as a consecutive substring? Well, yes, because I only have to look at each block of three consecutive letters to determine whether it contains $\text{cat}$ or $\text{dog}$. So this language ought to be (and is) regular.