3
$\begingroup$

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.

  • 0
    There is a [similar question on cs.SE](http://cs.stackexchange.com/q/2393/98).2012-06-17

2 Answers 2

4

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.

6

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.