tag:blogger.com,1999:blog-3722233.post3612114845983607594..comments2021-05-09T10:50:12.792-05:00Comments on Computational Complexity: Do we ever NEED the adv pumping lemma for Reg langs?Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger10125tag:blogger.com,1999:blog-3722233.post-43742689950030315772013-03-07T09:45:16.120-06:002013-03-07T09:45:16.120-06:00I believe that your family B(omega) is more or les...I believe that your family B(omega) is more or less the subject of the paper:<br /><br />Ginsburg, Seymour; Goldstine, Jonathan Intersection-closed full AFL and the recursively enumerable languages. Information and Control 22 (1973), 201–231.<br /><br />(They do not require closure under reversal in their definition; but otherwise it is basically the same.)<br /><br />Lemma 3.1 of this paper almost gives what you are looking for: i.e., a language L such that every language in B(omega) satisfies the pumping lemma; except here the pumping lemma satisfied is slightly weaker than the usual one due to the words "almost all" that appear in the statement of the lemma.<br /><br />Anyways, there's some interesting stuff there.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-4552013726504133432013-03-05T04:44:39.453-06:002013-03-05T04:44:39.453-06:00I think the pumping lemma for regular languages is...I think the pumping lemma for regular languages is not very useful. Instead you can always start with the assumption that you have an NFA with n states that accepts the language. Then show that this leads to a contradiction via pumping an accepted word of length >= n in any consecutive block of n letters (since some state is repeated). Yeah, you're basically repeating the proof of the pumping lemma, now for a specific language. But this does not take more time than applying the pumping lemma itself. So the lemma is useless in the sense that it does not give a shorter proof. <br /><br />Moreover, the students will be less bothered how to refute a lemma with this lots of quantifiers. (Actually, there is some use for this: the regular pumping lemma is a good exercise for applying the pumping lemma for context free languages).<br /><br />Another good option is to use the Myhill-Nerode theorem. (as already Paul Beame pointed out)Jochen Messnerhttp://www.htw-aalen.de/personal/jochen.messner/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-16259155568968105972013-03-04T21:49:58.838-06:002013-03-04T21:49:58.838-06:00Re Gasarch at 4:16 PM. I believe the following:
...Re Gasarch at 4:16 PM. I believe the following:<br /><br />Advanced pumping does not show that language to be non-regular. However, I believe that closure properties do. Specifically, I think you can intersect with the regular expression 01(11)*001(11)*01. That's a 0, an odd number of 1s, two 0s, an odd number of 1s, and another 1. I believe that such a word is in the language only if the odd number of 1s are the same, and then this language falls under the (weaker) pumping lemma.<br />Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-58185391573225601122013-03-04T16:18:01.637-06:002013-03-04T16:18:01.637-06:00It is a fine question but ... why even bother with...It is a fine question but ... why even bother with any version of the pumping lemma when the lower bound one gets from the easy direction of the Myhill-Nerode Theorem is (1) optimal and (usually) (2) more intuitive than and at least as easy to use as the pumping lemma?Paul Beamenoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-72641543981796162072013-03-04T16:16:09.799-06:002013-03-04T16:16:09.799-06:00The first paper you propose gives a very good cand...The first paper you propose gives a very good candidate:<br /><br />{ x x^R w | x,w \in {0,1}^+ }<br /><br />Pumping does not show it is non regular.<br />Does adv pumping?<br />Does closure propoerties- that is, if we start the B-hierarchy with this<br />lang, do we eventually get a lang that can be shown non-reg via pumping or adv pumping?GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-20777348528101337412013-03-04T15:58:49.713-06:002013-03-04T15:58:49.713-06:00ad other techniques to show langs not regular - se...ad other techniques to show langs not regular - see the non-pumping lemma:<br />http://www.csie.nctu.edu.tw/~ymhuang/formal_language/papers/the-end-of-pumping.pdf<br />http://cci.case.edu/cci/images/6/65/171-generalized-non-pumping.pdf<br />there are non-reg. languages which satisfy the conclusion of pumping lemma and not the non-pumping lemma and vice versaAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-19176972621910661532013-03-04T15:49:12.248-06:002013-03-04T15:49:12.248-06:00anon 1:01. Your lang does not answer Question 1. I...anon 1:01. Your lang does not answer Question 1. Intersect your lang<br />with a^* c b^* to get a^n c b^n which can be shown non-reg by the pumping lemma.<br /><br />Anon 1:41. Parikh's theorem is on context free langs.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-66693711751929322472013-03-04T13:41:10.288-06:002013-03-04T13:41:10.288-06:00Which did Parikh do?Which did Parikh do?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-20044856678556241272013-03-04T13:01:19.413-06:002013-03-04T13:01:19.413-06:00@Anonymous above me: L:= {a^ncc^*b^n | n \in N}. T...@Anonymous above me: L:= {a^ncc^*b^n | n \in N}. The role of y is only played by strings consisting of one or more c's. But the a and b part become arbitrarily long. I think this is also an answer for question 1.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-58773487493524625422013-03-04T11:56:10.363-06:002013-03-04T11:56:10.363-06:00What about Rigorous Question 0: Is there a languag...What about Rigorous Question 0: Is there a language L that satisfies the pumping lemma but not the advanced pumping lemma?Anonymousnoreply@blogger.com