tag:blogger.com,1999:blog-3722233.post5995093963885597380..comments2024-03-28T18:17:00.135-05:00Comments on Computational Complexity: I left Push Down Automata out of my class and learned some things!Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger17125tag:blogger.com,1999:blog-3722233.post-42332557289756936412012-04-29T00:39:56.309-05:002012-04-29T00:39:56.309-05:00I would leave CFG out also. They are not needed fo...I would leave CFG out also. They are not needed for the rest of the course, a modern introduction to computability and complexity theory doesn't need them. The same way we do not teach general recursive models we don't need to and should not teach CFL/CFG/PDA anymore.<br /><br />It is true that they might be useful for some other areas (Computational Linguistics, Compilers, ...) but why should they be taught in an introduction to computability and complexity course considering the amount of pressure at universities to reduce the number of required theory courses? They can teach CFL in their courses if they need them. There are too many interesting topics in computability and complexity that I don't think teaching CFL in such a course make sense anymore. They are nice results but they are not the only ones that are left out of an introduction course to computability and complexity. I would prefer to teach students topics that would get them interested in learning about modern complexity theory.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-57390940613488900782012-04-28T21:49:04.490-05:002012-04-28T21:49:04.490-05:00One way of leaving pdas out -- but not really -- i...One way of leaving pdas out -- but not really -- is to do semirings. More precisely:<br /><br />1. When doing finite automata, do also probabilistic finite automata. (This is a good idea anyhow, since they are quite useful under the name of Hidden Markov Processes with our Machine Learning friends.)<br /><br />2. The algorithm to get regular expressions from finite automata is also an algorithm for shortest paths, and an algorithm to compute transition probabilities for probabilistic automata.<br />A version of the process associates nonterminals with each state, that generate the languages accepted from that state. The whole thing can be expressed as a set of (recursive) equations in languages. These systems can be solved algebraically. (Essentially, instead of inverses, compute fixpoints.)<br /><br />3. These recursive equations turn out to be left recursive for regular languages, and left recursion can be eliminated.<br /><br />4. The same process works for cfls. The recursion cannot be eliminated in general, but students have already learned that you implement recursion with stacks. You may then comment that there is a version of automata that does this, called pda.<br /><br />The advantage of this approach is that you show that Theory can do fun and interesting things. Many students leave a standard Formal Languages course convinced that Theory consists in long uninteresting inductive proofs on the length of something, and they always prove some trivial fact. The approach above throws in a bunch of interesting, nontrivial (but not very hard) facts and constructions.Janos Simonnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1905646252161982922012-04-28T10:22:53.413-05:002012-04-28T10:22:53.413-05:00You do not need Chomsky normal form. Just change a...You do not need Chomsky normal form. Just change all rules<br /><br />S -> A1 A2 ... An<br /><br />to<br /><br />[p1, S, p(n+1)] -> [p1, A1, p2] [p2, A2, p3] ... [pn, An, p(n+1)]<br /><br />for all appropiate sequences of states pi (do not change nonterminals). Like another Anonymous I came up with it myself when I was an undergraduate.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-9033022608216486512012-04-27T16:33:15.813-05:002012-04-27T16:33:15.813-05:00you guys teach complexity theory,sometimes advance...you guys teach complexity theory,sometimes advanced complexity theory,theory of computation and many other very very important,fundamental and basic subjects in theoretical computer science but students like us,meaning from a remote country and self learners,could not avail yours great teaching.you guys should video tape(record)them and make them publicly available.look at MIT OCW,it helped people all over the world the way people learn and its doing a great job but alas,mit ocw doesn't have advanced courses like complexity theory,approximation algo's video so being great researcher in theoretical computer science and a good teacher,you guys should make your class video available.lance,you are teaching Topics in Computational Complexity this semester,now nice it would be if you make this class available to the whole world.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-75150229566296599692012-04-27T06:12:52.845-05:002012-04-27T06:12:52.845-05:00I am largely self-taught in language theory: I am ...I am largely self-taught in language theory: I am doing a Master's degree in regulated rewriting, but on context-free and regular languages, I have learned mostly from the internet (and what I skimmed from Sipser while researching an undergraduate project on P vs. NP).<br /><br />Until I tutored a course in formal languages, I had only the vaguest idea of PDAs. I find the concept of a context-free grammar exceedingly elegant, while PDAs are relatively meaningless for me (essentially, I feel the opposite of Comp Sci Student above). While tutoring this course, I also found that many struggled with non-determinism (the course didn't cover NFAs -- but NFAs are anyway more easily understood as "there exists a path labelled blah" than as matching machines, IMO). They also aren't particularly useful for practical parsing. So I say skip 'em<br /><br />Your proof of CFL being closed under intersection with REG is the one I came up with myself (of course it wasn't original with me -- in fact until now I had assumed it was the standard proof); it also generalises nicely to larger grammars (with restricted rewriting, etc.).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-23297868423457381192012-04-26T21:31:24.315-05:002012-04-26T21:31:24.315-05:00> because the whole point of doing CFL's at...> because the whole point of doing CFL's at all is they can be designed to be processed with a stack.<br /><br />Hmm, I see what you're saying in terms of stressing the parsing connection, but I think there's other educational value in CFLs. If you are interested in introducing formal grammars (or any generative system outside of regular languages), CFGs seem like the ideal flavor. They're simple enough to understand derivations, complicated enough to provide some tricky problems, and used in practice.Lucas Cookhttps://www.blogger.com/profile/11004240610526118411noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-34890148082709210282012-04-26T11:27:25.944-05:002012-04-26T11:27:25.944-05:00I think it's important to define PDA's and...I think it's important to define PDA's and do the CFG-to-PDA direction of the equivalence, because the whole point of doing CFL's at all is they can be designed to be processed with a stack. (I usually tell my students my opinion that in 500 years, if we have a civilization at all, Chomsky will be completely forgotten as a political figure, possibly remembered as a linguist if he turns out to have been mostly right, but definitely remembered as a mathematician for finding the CFG-PDA equivalence.<br /><br />I think the PDA-to-CFG proof is of only technical interest, though I always do it. Your new argument is a good contribution -- useful if you are committed to proving what you use and want to skip PDA-to-CFG.<br /><br />It's interesting that you appear to have done the Warshall-like construction for DFA-to-RegExp as Justin Kruskal (any relation?) used it in his argument. I always skip this because state elimination works so much better on any actual examples.<br /><br />If I were cutting back on the formal language section of this course I would consider dumping CFL's entirely.DaveMBhttps://www.blogger.com/profile/00779581893863396042noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-34500058188238689842012-04-26T11:20:58.602-05:002012-04-26T11:20:58.602-05:00As a student I'd prefer if PDAs were left in t...As a student I'd prefer if PDAs were left in the course.<br />CFGs are often confusing and it isn't obvious why some languages can be derived and others can't be. Without seeing them as a machine, I fear I would never have understood them.Comp Sci Studentnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-17030328544534765072012-04-26T11:01:40.394-05:002012-04-26T11:01:40.394-05:00In response to question #1, we've been repeate...In response to question #1, we've been repeatedly toying with leaving out PDAs in the UIUC ToC course (which is usually done in the style of the Sipser text). Proofs, grading, PDA-->CFG equivalence are all painful. There's an argument that the machine hierarchy is nonintuitive and thus valuable to teach, but I think you miss the early semester student attentiveness (ESSA..y?) if you dwell on DFAs or PDAs for too long.Lucas Cookhttps://www.blogger.com/profile/11004240610526118411noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-63810624786621301172012-04-26T10:38:57.131-05:002012-04-26T10:38:57.131-05:00I like having students develop (through homework p...I like having students develop (through homework problems) the notion of a counter automaton. They are a useful abstraction for problems involving # of a's, b's, c's (which can come in any order). It's easy to simulate a counter using a stack, but I imagine it would be very tedious to do directly in a CFG.mikeronoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-17960719396480213002012-04-26T10:14:16.344-05:002012-04-26T10:14:16.344-05:00Nice proof! Small typo: in Lemma 2.3, L should be ...Nice proof! Small typo: in Lemma 2.3, L should be declared regular.Zachary Abelhttp://blog.zacharyabel.comnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-15000774456625709072012-04-26T09:57:25.806-05:002012-04-26T09:57:25.806-05:00The Bar-Hillel et al. paper is reprinted in two bo...The Bar-Hillel et al. paper is reprinted in two books:<br /><br />Yehoshua Bar-Hillel. 1964. Language and information: selected essays on their theory and application. Addison-Wesley.<br />http://books.google.co.jp/books?ei=iV-ZT_7MIrGImQX4taSOBg&id=9WdZS5U40SwC&dq=Language+and+Information&q=intersection<br /><br />Robert Duncan Luce, editor. 1963. Readings in mathematical psychology, vol. 2. Wiley.Makoto Kanazawahttp://research.nii.ac.jp/~kanazawa/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-40018958636122193512012-04-26T09:52:22.022-05:002012-04-26T09:52:22.022-05:00This is a classical proof: Essentially the same pr...This is a classical proof: Essentially the same proof was already in Bar-Hillel, Perles, and Shamir, _On formal properties of simple phrase-structure grammars_, Zeitschrift für Phonetik, Sprachwissenschaft, und Kommunikations-forschung vol. 14, 1961.<br /><br />In particular, if you also show that emptiness of the language of a CFG is in linear time, this proof yields an O(|G|.|w|^3) time parsing algorithm by seeing the input string w as an automaton with |w|+1 states---for efficiency reasons you need to use a quadratic form on G (all productions have at most two symbols in their right-hand side) rather than Chomsky normal form, which can incur a blow-up in the size of the grammar.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-14609871146454566102012-04-26T09:38:09.063-05:002012-04-26T09:38:09.063-05:00This proof is often called the "Bar-Hillel co...This proof is often called the "Bar-Hillel construction" in computational linguistics and is quite well known. (It is the basis of approaches to parsing known as "parsing as intersection".) I believe it first appeared in<br /><br />Bar-Hillel, Y., M. Perles, and E. Shamir. 1961. On formal properties of simple phrase structure grammars. Zeitschrift für Phonetik, Sprachwissenschaft und Kommunikationsforschung 14(2): 143-172.<br /><br />I don't have the paper handy, but if I'm not mistaken, this is the paper that first proved the pumping lemma.Makoto Kanazawahttp://research.nii.ac.jp/~kanazawa/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-13148566003951435822012-04-26T09:31:29.818-05:002012-04-26T09:31:29.818-05:00Anon 1: Thanks. Is his proof essentially the same ...Anon 1: Thanks. Is his proof essentially the same as the one I present?<br /><br />Anon 2: Thanks. I have changed the title.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-84779496101704052062012-04-26T09:25:38.289-05:002012-04-26T09:25:38.289-05:00The title of your note is not meaningful. It jus...The title of your note is not meaningful. It just says that regular languages are context free which you asked your students. It should say that <br />{x \cap y | x\in CFL, y\in REG} = CFL.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-73924013009128253392012-04-26T08:27:54.649-05:002012-04-26T08:27:54.649-05:00A proof that context-free languages are closed und...A proof that context-free languages are closed under intersection with regular sets, that use only context-free grammars (not PDAs) can be found in<br /><br />A. Salomaa. Formal Languages. ACM Monograph Series, 1973.<br /><br />on page 59; there its Theorem 6.7.<br /><br />Best regards.Anonymousnoreply@blogger.com