Pumping Lemma: If a language L is regular, then there exists a number p ≥ 1 (the pumping length) such that every string uwv in L with |w| ≥ p can be written in the form uwv = uxyzv with strings x, y and z such that |xy| ≤ p, |y| ≥ 1 and uxyizv is in L for every integer i ≥ 0.
Myhill-Nerode: Given a language L, and a pair of strings x and y, define a distinguishing extension to be a string z such that exactly one of the two strings xz and yz belongs to L. Define a relation RL on strings by the rule that x RL y if there is no distinguishing extension for x and y. It is easy to show that RL is an equivalence relation on strings, and thus it divides the set of all finite strings into equivalence classes.
The Myhill–Nerode theorem states that L is regular if and only if RL has a finite number of equivalence classes, and moreover that the number of states in the smallest deterministic finite automaton (DFA) recognizing L is equal to the number of equivalence classes in RL. In particular, this implies that there is a unique minimal DFA with minimum number of states.
The two basic complaints about the pumping lemma: Five quantifiers and it is not complete--there are nonregular languages that can be pumped. To the first point if you think of the pumping lemma as a game with the adversary choosing p, x, y and z, the quantification is not as confusing as some would think. Myhill-Nerode also has five quantifiers when you spell it out: For all regular L, there exist x1,...,xk such that for all y there is an i such that for all z, xiz is in L iff yz is in L.
As to the second part, the counterexamples are contrived and usually go away with simple closure properties. Consider the one from wikipedia:
Take L ∩ (01(2∪3))* eliminates the strings in the first part of L and now it is easy to pump.
So I don't buy the arguments for Myhill-Nerode over pumping. Nevertheless I'll teach the pumping lemma and Myhill-Nerode because they are both so cool.
The point of the pumping lemma version is that it is useful when you get to CFGs, and with some reservations to Multiple Context-Free Grammars.
ReplyDelete(See Makoto Kanazawa's recent work on pumping lemmas for MCFGs).
Pumping is better pedagogically- it makes intuitive sense that its true
ReplyDeleteand the Pumping Lemma for CFG's is a nice followup.
Myhill-Nerode is more elegant and better mathematically.
One should not confuse what is better pedagogically and what is better
mathematically.
I disagree about pedagogy if you aren't going to do the PL for CFGs. (I no longer have time for that, or for the use of closures to prove non-regularity). Proving the whole of Myhill-Nerode is overkill if you are comparing it to the PL. All you need to show is that if two strings are not equivalent under R_L then they must lead to different states in any DFA for L, which is trivial.
ReplyDeleteThe only tricky part of this is getting students to understand R_L but the notion is very intuitive: If you are building a DFA for L then you think operationally about what you need to remember about prefixes of the input in order to figure out whether the whole string ought to be accepted. R_L captures exactly that issue so it fits with their DFA design ideas.
With Myhill-Nerode, you simply count the number of distinguishing extensions and you get the right answer. Usually, it is not hard to count this more or less exactly.
ReplyDeleteTo prove a language is irregular with the Pumping Lemma, you have to guess the correct original string to use. And there might not be any such string, because the Pumping Lemma isn't complete. I find this situation very confusing and frustrating.
I find the communication complexity view of Myhill-Nerode much more intuitive: Alice gets a string x, Bob a string y, and the goal is to find out if xy is in L. L is regular iff the one-way communication complexity of this problem is finite, i.e., the communication matrix has only finitely many distinct rows. To see that a language like {a^nb^n: n in N} is not regular consider all rows labeled with a^i and columns labeled with b^j, and it is an infinitely sized identity matrix.
ReplyDeleteYour formulation of the pumping lemma can be strengthened to u,v being the empty strings. Perhaps you're being confused by the Bar-Hillel pumping lemma?
ReplyDeleteRegarding which one is better, students are often confused by the fact that the adversary gets to choose the partition xyz. So on the one hand, if they do understand it then their mathematical level has increased. On the other hand, they usually don't get it. I haven't had the opportunity to compare the pumping lemma to Myhill-Nerode, so I can't say whether the latter is better, but I find it completely backwards that the simpler Myhill-Nerode criterion is not taught while the more complicated pumping lemma "test" is taught. I would go *first* for Myhill-Nerode, which I feel is more natural.
I teach finite automata and regular languages in two different courses. In the discrete math course, it comes at the end and I do only Myhill-Nerode. For the Sipser-book course, it comes at the beginning and I do both. (It's nice that Sipser 2e and 3e have M-N as a worked exercise.)
ReplyDeleteIn the discrete math course I'm doing this material to show that the techniques we've learned all term can solve actual mathematical problems related to computation. M-N gives more intuition about regular languages, and helps in mnimizing DFA's which the students like.
In the Sipser course I'm in more of a hurry and the FA material is review for many of them. I am going to do the CFL Pumping Lemma later in that course, so I want to do the regular language PL to have as a base for that. But as Lance says, they are both so cool, so I do M-N. I would rather have them use M-N for non-regularity proofs because they strike me as far more intuitive: the intuition that "you have to remember how many a's you've seen because if you don't know you are screwed if you get a particular number of b's" is really almost an M-N proof as it stands.
Anonymous makes a good point about communication complexity. I would not be surprised if in the future everyone does communication complexity in undergrad courses. Does anyone do that now, or want to argue that we should or shouldn't?
I never understood on which grounds people claim that doing games with adversaries and the likes is "more intuitive" than quantification. It is quite clear that quantification is much more elegant and transparent than games.
ReplyDeleteI need code of DFA to Pumping lemma ...Give Transition table of DFA As input and get three strings that will accept pumping lemma...
ReplyDelete