# How to feel intuitively that a language is regular

Given a language $L= \{a^n b^n c^n\}$, how can I say directly, without looking at production rules, that this language is not regular?

I could use pumping lemma but some guys are saying just looking at the grammar that this is not regular one. How is it possible?

• Anybody can look at any language and just say that it's not regular. I'm not sure intuition, per se, is as much at play here as is experience. This is a fairly simple language (despite being non-regular) and is one that is inevitably encountered in the study of formal languages. Once you've been told that it's not regular, and have proven that it's not regular using any valid proof technique, you typically don't need a proof to convince other people, because they all proved it themselves when they were being introduced to the subject. Jun 16, 2012 at 16:18
• yeah, but sometimes in lectures they just follow some dry mathematical proves, but they really lack intuitional explanations with real simple examples Jun 16, 2012 at 16:47
• Forget $a^nb^nc^n$. Did you ever get to feel that $a^nb^n$ is not regular? Jun 17, 2012 at 12:39
• Looking at a grammar and proclaiming because the grammar is not regular the language is not regular is a fallacy. There are plenty non-regular grammars for regular languages. Beware! That said, deciding whether a grammar is regular is easy; just check the productions.
– Raphael
Jun 17, 2012 at 12:58
• There is a similar question on math.SE.
– Raphael
Jun 17, 2012 at 16:25

The main property of DFA's/NFA's is the lack of unbounded memory. If you look at a language and the only algorithm (which should later be translated into a Finite Automaton) you can think of requires this property, that is, you feel that any algorithm that recognizes it will need to remember an arbitrary large number of things (like $n$ in your example) then that language is probably not regular.

Of course, you should always remember that mathematical intuition can be wrong, and the only way to be sure of your intuition is to prove it.

EDIT: I'll answer the last question in the comments here, because of lack of space.

you guys are talking about unbounded memory which you mean is the reason why it is not regular. but a^nb^m can also have unbounded memory if i want, doesnot it? this is still giving me no peace.

The issue is not how big the words can get (you will usually encounter infinite regular languages, because every finite language is regular, and that's pretty boring) but how much the DFA needs to remember.
In the $a^mb^n$ example, there is no need to remember $m,n$. The algorihm just needs to make sure they are positive and that the word is correctly ordered. This is a finite list, and each of the items on the list requires a constant amount of memory.
Compare this to $a^nb^n$, for which a simple alogrithm is required to remember that the number of $a$'s is equal to the number of $b$'s. This will require unbounded memory. When I look at a language and see that any algorithm I can think of needs unbounded memory, my intuition that the language is not regular grows stronger. If I can't find a "smart" algorithm (one that requires a constant amount of memory) in a reasonable amount of time (how much time is reasonable is up to you) I will try proving the language is not regular.
Hope this makes it a bit clearer.

• thank you, mathematical proves bring the intuition, but look at this production rule: S -> ab | aSb. this is for a^nb^n which says that it is also not regular. but a^mb^n is regular with m,n>=1. why is this? these are actually the same form, right? i dont understand the difference between these two languages Jun 16, 2012 at 16:45
• For a^nb^n you need to keep track of 2 things: first, that the number of a's equals the number of b's (this is the impossible part for DFA's), and second that no 'b' is followed by an 'a'. For a^mb^n you don't care about the value of m,n. You only care that there is at least one 'a' and at least one 'b' and that no 'b' is followed by an 'a'. Informally speaking, you need to remember only 3 thing. Jun 16, 2012 at 17:07
• oh okay, now i got it. Jun 16, 2012 at 18:01
• so the order is also the crucial thing, right? like aabbcc accepted but not aabcbc only because the order is not okay. right? Jun 16, 2012 at 18:19
• "The main property of regular languages is the lack of unbounded memory." -- I know what you mean, but that sentence does not make any sense. "you feel that any algorithm that recognizes it will need to remember an arbitrary large number of things" -- This is indeed the only intuition I know, too, but its kind is very, very dangerous; see here.
– Raphael
Jun 17, 2012 at 13:00

I could use pumping lemma

Exactly. After you have used the Pumping lemma or any of the other techniques a couple (of dozens) of times, you will start seeing the patterns in languages that prohibit them from being regular. $a^n\dots b^n$ is a very basic one you probably have mastered already. So this is also a matter of experience, not only intuition.

A good way to test your intuition is looking at these languages:

1. $\quad \displaystyle \{xyyz \mid x,y,z \in \{a,b\}^+\}$
2. $\quad \displaystyle \{xyyz \mid x,y,z \in \{a,b\}^*\}$
3. $\quad \displaystyle \{xyyz \mid x,y,z \in \{a,b,c\}^+\}$
4. $\quad \displaystyle \{xyyz \mid x,y,z \in \{a,b,c\}^*\}$

Which are context-free?

• If somebody knows similarly nice examples for the border of regular languages, please say so. Please don't spoil the answer in the comments.
– Raphael
Jun 17, 2012 at 13:10
• Raphael - great job! thank you for giving examples and for testing me explicitly. Jun 17, 2012 at 21:23
• @doniyor let us continue this discussion in chat
– Raphael
Jun 18, 2012 at 12:16

You can actually decide if a language is regular using fairly straightforward calculations, rather than doing a full proof. You simply need to apply one very powerful criterion: A language is regular if and only if it has finitely many quotients.

Intuitively, a quotient is what you need to complete a word after having already read in part of the input. More formally, the left quotient of a language $L$ by a string $x$, written $x\setminus L$ is the set of strings $w$ such that $xw \in L$. For example, if $L=\{a^nb^n\}$, then $a\setminus L= \{a^{n-1} b^n | n\ge 1 \}$, while $b \setminus L=\emptyset$. We can easily see that $a^k \setminus L = \{a^{n-k}b^n | n \ge k \}$. There are infinitely many quotients of the form, so it follows immediately that $L$ is not regular.

If we construct a DFA $D$ to decide L, and $D$ will be in state $S$ after reading in $a$, then $a\setminus L$ is the language decided by $D$ modified to have start state $S$. This same idea can be used to directly construct the minimal DFA that decides a regular language from its definition.

• b\L means: if i devide the L by b, then i will get empty set?. is it because i actually have to start reading the word from begining? and not from behind? Jun 22, 2012 at 14:22
• $b\setminus L=\emptyset$ because there are no strings in L that start with B. You can define a right quotient $L/b$ similarly which corresponds to "reading from behind." A language is also regular iff it has finitely many right quotients, because the reversal of a regular language is regular. (This is easy to show using NFAs.) Jun 23, 2012 at 3:21
• Here's a good slide deck which explains quotients, and how to construct DFAs from them: cs.cmu.edu/~cdm/pdf/Minimization.pdf Jun 23, 2012 at 3:23
• oh okay, thanks a lot. now i get a litle. mmm... let me study this again for a while though... Jun 23, 2012 at 5:01