9
$\begingroup$

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?

|cite|improve this question|||||
$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Patrick87 Jun 16 '12 at 16:18
  • $\begingroup$ yeah, but sometimes in lectures they just follow some dry mathematical proves, but they really lack intuitional explanations with real simple examples $\endgroup$ – doniyor Jun 16 '12 at 16:47
  • $\begingroup$ Forget $a^nb^nc^n$. Did you ever get to feel that $a^nb^n$ is not regular? $\endgroup$ – Uday Reddy Jun 17 '12 at 12:39
  • 2
    $\begingroup$ 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. $\endgroup$ – Raphael♦ Jun 17 '12 at 12:58
  • $\begingroup$ There is a similar question on math.SE. $\endgroup$ – Raphael♦ Jun 17 '12 at 16:25
11
$\begingroup$

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.

|cite|improve this answer|||||
$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – doniyor Jun 16 '12 at 16:45
  • 1
    $\begingroup$ 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. $\endgroup$ – Boris Trayvas Jun 16 '12 at 17:07
  • $\begingroup$ oh okay, now i got it. $\endgroup$ – doniyor Jun 16 '12 at 18:01
  • $\begingroup$ so the order is also the crucial thing, right? like aabbcc accepted but not aabcbc only because the order is not okay. right? $\endgroup$ – doniyor Jun 16 '12 at 18:19
  • 1
    $\begingroup$ "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. $\endgroup$ – Raphael♦ Jun 17 '12 at 13:00
5
$\begingroup$

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?

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

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.

|cite|improve this answer|||||
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – doniyor Jun 22 '12 at 14:22
  • 1
    $\begingroup$ $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.) $\endgroup$ – James Koppel Jun 23 '12 at 3:21
  • 1
    $\begingroup$ Here's a good slide deck which explains quotients, and how to construct DFAs from them: cs.cmu.edu/~cdm/pdf/Minimization.pdf $\endgroup$ – James Koppel Jun 23 '12 at 3:23
  • $\begingroup$ oh okay, thanks a lot. now i get a litle. mmm... let me study this again for a while though... $\endgroup$ – doniyor Jun 23 '12 at 5:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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