5
$\begingroup$

Why is $L= \{ 0^n 1^n | n \geq 1 \}$ not regular language? looks like a duplicate of How to prove that a language is not regular? at the first glance if you are an expert. I would argue though, they are two very different questions, even though there's a huge overlap.

How to prove that a language is not regular? is asking for a formal treatment of regular languages, and the answer, while helpful to many, isn't helpful if you don't understand much of the formal semantics involved in TCS if you are just starting out. My question, Why is $L= \{ 0^n 1^n | n \geq 1 \}$ not regular language? is asking for a very informal, and easy to understand explanation, hopefully without the formalism needed to understand the former question, that why a specific language which was presented in a automata lecture, not a regular language. (So far Artem's answer in the comment section made the most sense) IMO, the two questions is asking for a completely different kind of answer, even though they have huge overlap, so I would argue they are not exact duplicates. They look duplicate to an expert, but for novices, the question "How to prove that a language is not regular" wouldn't even come cross your mind when you have question about why language X is not regular.

(There may be other problems with the question, which makes it unsuitable for SE, I'm just arguing that it's not an exact duplicate though)

$\endgroup$

4 Answers 4

6
$\begingroup$

When taking the question at face value, it does look like a duplicate.

If you don't think it's a duplicate (I expect you were after something like Kaveh's answer?), you should mention the existing question in your question and explain how the existing question doesn't satisfy you. Somethin like this:

I've read <link>, but it doesn't address my question. I'm not looking for a proof technique: I've seen a proof, and I understand each step, but I don't get the intuition. Is there a good intuition that shows that this particular language is not regular?

The question has been edited and reopened based on the apparent dominant opinion on Meta.


Speaking of that reference question, I have a concern with the answers. They're all fairly advanced, tough reading for an undergraduate student.

  • Romuald's answer (accepted) has the right material, but it is extremely terse. It's more of a table of contents than a full answer at the level I'd expect.
  • Dave Clarke's answer is good and easy to follow, but it only covers one example of the pumping lemma, and it's a bit close to the metal without showing the intuitions that the learning student would need to acquire.
  • Louis's answer is very good at showing the intuition behind the pumping lemma, but the gap between that and writing a proof is rather wide. (Hmmm, combined with Dave's answer, it's not too bad.)
  • Ran G.'s answer is the most didactic presentation of the pumping lemma on this page, but doesn't go beyond this, and may be harder to follow than Dave's for a beginner.
  • Raphael's answer is at another level altogether.

“How do I prove that this language is not regular” is very often asked by an undergraduate student who is only now studying the topic for the first time. We have good answers, but somewhat missing their target audience. Should we do better? Can we?

$\endgroup$
1
  • $\begingroup$ I think reading and then doing some (or many) of those proofs is what helps the most. It might not help everybody, though. I suspect that diluting the proofs too much will help in the long run; I have seen too many people use the "intuitions" and "tricks" as if they were the real thing. In the end, I don't think SE is a good platform if you want to learn some topic from scratch; it is good for focused questions. (Regarding my answer, I don't think it is "on another level" but merely not widely known. It is often easy to execute, but hard to understand fundamentally.) $\endgroup$
    – Raphael Mod
    May 16, 2012 at 23:26
3
$\begingroup$

This was suppose to be a comment on @Raphael's answer, with which I strongly disagree:

In my day-to-day activities I do more than churn symbols and do formal calculations and proofs. Above all else, my success or failure depends not on my ability to formally manipulate Greek letters, but on the intuitions I have and how useful they are. Thus, a question asking for intuitions is perfectly valid, and if someone answers a request for intuition with a formal proof without and intuitive argument to back it, then their answer should be down-voted as not answering the question.

When you are experienced with TCS it is easy to jump back and forth between Greek and intuition. When you are learning, this becomes a very important (and often difficult) skill to acquire! We should encourage students by reminding them that TCS is not an impenetrable fortress of formal symbols, but that the formal symbols are just our tools to express and test our intuitions.

As for the case of Ken Li's question, it was very poorly formulated. As it was formulated, it did not ask for intuition and thus an application of the pumping lemma would have been a valid answer; hence I think it was justified to close the question. If the question read something like:

"I know that ${ 0^n 1^n | n \geq 1 }$ is not regular, and I can carry out the standard pumping-lemma proof to prove it. However, I don't grok this: what is the intuition behind why we would expect the language to be not regular?"

Then it would not be an exact duplicate, and a simple pumping lemma proof would be an incorrect answer.

$\endgroup$
4
  • $\begingroup$ Of course intuition is important. However, I have found it difficult to convey my intuition to someone in front of the same whiteboard, let alone via written text. People work so differently. But then, maybe I am just a bad explainer/teacher. $\endgroup$
    – Raphael Mod
    May 16, 2012 at 23:20
  • 2
    $\begingroup$ Upvoted. @Raphael: Exactly! Different people work differently, and communicating intuition is hard. That does not mean that we (the community) should not try, or that requests for intuition are useless, even after a formal proof is "clear". $\endgroup$
    – JeffE
    May 19, 2012 at 6:48
  • $\begingroup$ @JeffE: The point is that SE questions should have a somewhat correct answer. There is always room for personal preference and style, but the effect is way stronger for intuition questions; they might be too far from the SE ideal to be helpful (for future visitors, in particular). $\endgroup$
    – Raphael Mod
    May 20, 2012 at 10:45
  • 2
    $\begingroup$ Honestly, I think you're sticking to "the SE style" a little too strongly. Answers are supposed to be useful. A useful answer that isn't perfectly correct is far better than an answer that is perfectly correct but opaque. $\endgroup$
    – JeffE
    May 20, 2012 at 17:04
-3
$\begingroup$

Usually those "why..." questions end up accepting a proof, so I closed as duplicate (following existing flags).

In general, I often do not see the point in those questions; the statement holds because it holds. They can be made interesting by providing context: "Why is A regular but B is not? They look so similar!" because then an answerer can exhibit the difference.

As a "flat" question I do not see good answers that are not "trivial" or need some working knowledge of the involved formalisms (in this case, a characterisation of what NFA can do). You are asking a question about a formal creature, after all, and don't tell us what knowledge we can assume.

$\endgroup$
-4
$\begingroup$

Here's what's bound to be an unpopular answer.

Questions asking for different kinds of answers to the same underlying question should be closed as duplicates, and with extreme prejudice. They may then either be left as sign posts or deleted, potentially merging good answers and/or elements of the question into the main thread. Help comes in many forms, some of which may not be expected by the person asking the question.

More generally, requests to artificially restrict the form (rather than focus on specified content) should not be honored. For instance, requests for hints to questions with full answers need not be honored (hints may be given, but full answers should not be penalized); requests for intuition rather than formalism may likewise be ignored.

When people ask questions and provide answers here, that becomes the property of the community. Is it right to give somebody your hat and then demand that they wear it backwards? I suppose one could make a convincing analogy to copyleft licenses, but I digress. IMHO, there is no place for these kinds of restrictions on the form of answers. Real or implied restrictions should be removed from all questions (though this does not address the question of how to draw a meaningful distinction between form and content).

$\endgroup$
6
  • 3
    $\begingroup$ I disagree. As answerers, we are not obliged to answer. If we can't answer the specific question of "What is the intuition behind blah" then we can just move on with our lives and answer a different question. Especially with formal languages, students often learn how to do the arithmetic gymnastics without ever understanding why they are doing them. Imagine the analogous case in physics: what if you were not allowed to ask for physical examples or physical intuition on certain problems and equations? $\endgroup$ May 17, 2012 at 14:06
  • 4
    $\begingroup$ I agree with you in principle, but “how do I prove this” and “what's the intuition behind this” are different questions, not just asking for different kinds of answers. $\endgroup$ May 17, 2012 at 16:40
  • $\begingroup$ @Gilles I'm not sure I agree they're different questions. The real question is "why X?" Answers may provide "intuition" or proofs, or hints, or whatever is helpful to answer the question. Questions of the form "Why X? Only proofs, please!" Should get the same treatment, IMHO, as questions asking for hints or intuition or pig Latin: ignore the request, and proceed accordingly. $\endgroup$
    – Patrick87
    May 17, 2012 at 19:16
  • 3
    $\begingroup$ @Patrick87 I disagree. If someone asks “how do I prove X” and someone answers “intuitively speaking, here's why it's true: …”, that is not a proper answer. $\endgroup$ May 17, 2012 at 19:26
  • 3
    $\begingroup$ @Patrick87 Unfortunately, there are proofs that do not answer the "why?" question on an intuitive level at all, unless you have lots of intuition in the area already. Usual culprits are indirect and non-constructive proofs. $\endgroup$
    – Raphael Mod
    May 19, 2012 at 10:24
  • $\begingroup$ /unless/even if/ $\endgroup$
    – JeffE
    May 24, 2012 at 21:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .