Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
2  
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

2 Answers 2

up vote 4 down vote accepted

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.

share|improve this answer

Are you saying that you know how to prove if a language is regular, and you know how to prove that a language is irregular, but you don't know how to decide which strategy to try? Then try both! Try one strategy for awhile, then try the other. Guessing is a time-honored mathematical strategy.

As far as intuition goes, the informal test for regularity is "if I were given a huge string, could I figure out whether it's in the language by reading left to right without writing anything down?" Your working memory can in practice only hold a bounded amount of information so in practice if you're doing this you're running a finite state machine in your head.

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.

Example. Consider the Dyck language of correctly nested parentheses. The amount of nesting is unlimited, so to check for correct nesting I would potentially have to keep track of arbitrary many left parentheses which have not yet been matched to a right parenthesis. Thus this language ought not to be (and isn't) regular.

On the other hand, consider the language of correctly nested parentheses where we allow only a bounded amount of nesting. I only have to keep track of a bounded number of left parentheses. So this language ought to be (and is) regular.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.