Timeline for How to prove that a language is not regular?
Current License: CC BY-SA 3.0
18 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 13, 2017 at 12:48 | history | edited | CommunityBot |
replaced http://cs.stackexchange.com/ with https://cs.stackexchange.com/
|
|
| Apr 4, 2012 at 19:53 | comment | added | Dave Clarke | @Louis: I was trying to show a more general strategy with my example. But as you can see, there are many ways. | |
| Apr 4, 2012 at 19:47 | comment | added | Louis | The amount of editing that has been done to answer such an easy question makes me wonder why everybody teaches the pumping lemma as "the" way to prove non-regularity. Out of curiosity, why not just take your string to be something like $(01)^{2p}2^{2p}$? The pumping lemma tells you that $y$ has no $2$s in it, from which a contradiction is more straightforward. | |
| Apr 4, 2012 at 17:57 | comment | added | Dave Clarke | @Gilles: It's okay. I simply confused myself by not reading all of the changes you made. | |
| Apr 4, 2012 at 16:38 | comment | added | Gilles 'SO- stop being evil' | @Dave Feel free to revert if you don't like my edits. I thought this breakdown with less overlap between the cases was both easier to work with and more natural (either $y$ contains a $2$ or it doesn't, or in other words either $|z| \le p$ or $|z| < p$). | |
| Apr 4, 2012 at 16:31 | comment | added | Dave Clarke | @Gilles: I see that you have radically changed my answer, and now see what you mean. | |
| Apr 4, 2012 at 16:30 | comment | added | Dave Clarke | @Gilles: But it doesn't rule out any of the forms I enumerated. | |
| Apr 4, 2012 at 16:26 | comment | added | Raphael | I don't like Wikipedia's formulation; due to redundancy it is very verbose. | |
| Apr 4, 2012 at 16:25 | history | edited | Raphael | CC BY-SA 3.0 |
formatting
|
| Apr 4, 2012 at 16:19 | comment | added | Dave Clarke | Duh! I see it now. Thanks. It does not, however, rule out any of the forms of decomposition mentioned in the answer; it only limits what values of $k$ and $l$ I can take. | |
| Apr 4, 2012 at 15:32 | comment | added | Dave Clarke | @Gilles: I think that all the decompositions are possible, just that $k$ will be bounded. I'm not sure what it has to do with the length of $z$. | |
| Apr 4, 2012 at 15:30 | history | edited | Gilles 'SO- stop being evil' | CC BY-SA 3.0 |
I accidentally the verb
|
| Apr 4, 2012 at 15:28 | comment | added | Dave Clarke | @Gilles: I'm not even sure what the sentence you added means. | |
| Apr 4, 2012 at 15:25 | comment | added | Gilles 'SO- stop being evil' | An example where the hypothesis $|xy|\le p$ is needed would be nice. | |
| Apr 4, 2012 at 15:24 | history | edited | Gilles 'SO- stop being evil' | CC BY-SA 3.0 |
typos; mention the hypothesis |xy|<=p
|
| Apr 4, 2012 at 11:06 | history | edited | Dave Clarke | CC BY-SA 3.0 |
added 211 characters in body
|
| Apr 4, 2012 at 10:50 | history | edited | Dave Clarke | CC BY-SA 3.0 |
added 726 characters in body
|
| Apr 4, 2012 at 10:40 | history | answered | Dave Clarke | CC BY-SA 3.0 |