tag:blogger.com,1999:blog-3722233.post8360545076700365397..comments2023-09-25T11:29:10.548-05:00Comments on Computational Complexity: Myhill Nerode versus Pumping LemmaLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger9125tag:blogger.com,1999:blog-3722233.post-283293507012367222015-06-07T14:56:18.484-05:002015-06-07T14:56:18.484-05:00I need code of DFA to Pumping lemma ...Give Transi...I need code of DFA to Pumping lemma ...Give Transition table of DFA As input and get three strings that will accept pumping lemma...Anonymoushttps://www.blogger.com/profile/14506148492892365368noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-47678313175207925482013-09-09T05:16:41.728-05:002013-09-09T05:16:41.728-05:00I never understood on which grounds people claim 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.CS Profnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-55719834008861720472013-09-08T13:47:30.558-05:002013-09-08T13:47:30.558-05:00I teach finite automata and regular languages in t...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.)<br /><br />In 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.<br /><br />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.<br /><br />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?DaveMBhttps://www.blogger.com/profile/00779581893863396042noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-49628454532854555562013-09-08T13:43:56.611-05:002013-09-08T13:43:56.611-05:00Your formulation of the pumping lemma can be stren...Your 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?<br /><br />Regarding 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.Yuval Filmushttps://www.blogger.com/profile/08450062297306341505noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-28723121729885234652013-09-06T21:33:50.776-05:002013-09-06T21:33:50.776-05:00I find the communication complexity view of Myhill...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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-51567768745233241132013-09-06T17:08:08.304-05:002013-09-06T17:08:08.304-05:00With Myhill-Nerode, you simply count the number of...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.<br /> <br />To 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.Davidhttps://www.blogger.com/profile/13818371550669837787noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-4586468409621311212013-09-06T16:32:44.551-05:002013-09-06T16:32:44.551-05:00I disagree about pedagogy if you aren't going ...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. <br /><br />The 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. Paul Beamehttp://www.cs.washington.edu/people/faculty/beamenoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-37273952203979344512013-09-06T13:04:00.764-05:002013-09-06T13:04:00.764-05:00Pumping is better pedagogically- it makes intuitiv...Pumping is better pedagogically- it makes intuitive sense that its true<br />and the Pumping Lemma for CFG's is a nice followup.<br /><br />Myhill-Nerode is more elegant and better mathematically.<br /><br />One should not confuse what is better pedagogically and what is better<br />mathematically.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-19773385983019804622013-09-06T09:20:00.963-05:002013-09-06T09:20:00.963-05:00The point of the pumping lemma version is that it ...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.<br />(See Makoto Kanazawa's recent work on pumping lemmas for MCFGs).<br />Alex Clarkhttps://www.blogger.com/profile/04634767958690153584noreply@blogger.com