Timeline for Proving that the scramble of a regular language is context-free
Current License: CC BY-SA 3.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 10, 2016 at 21:43 | comment | added | Michael Wehar | Thanks again Yuval for the many follow-up comments. I appreciate it. :) | |
| Apr 10, 2016 at 20:27 | comment | added | Yuval Filmus | There are whole papers written on this very subject, which you can find using your favorite research engine. Unfortunately I'm not an expert in this area. | |
| Apr 10, 2016 at 20:26 | comment | added | Michael Wehar | Great! Thanks for the clarification. Next, how large are the y_i's in terms of the state complexity of the context-free language? 2^n or 2^n^2 maybe? | |
| Apr 10, 2016 at 20:24 | comment | added | Yuval Filmus | Yes, and is easy to prove (exercise). Just like articles have mistakes, so Wikipedia has mistakes, and it would be great if you could enhance Wikipedia by fixing any mistakes you find. | |
| Apr 10, 2016 at 20:23 | comment | added | Michael Wehar | But, the part afterwards saying there is a cummunatively equivalent regular language sounds reasonable. | |
| Apr 10, 2016 at 20:23 | comment | added | Yuval Filmus | Whoever wrote the article probably meant that every semilinear set can be "realized" by a regular language – in your case $(01)^*$. If you find a mistake in Wikipedia, go ahead and correct it – that's part of the features of Wikipedia. | |
| Apr 10, 2016 at 20:19 | comment | added | Michael Wehar | It says for any semiliner set, the language of words whose parikh vectors are in the set is regular. However, the language of stings with an equal number of 0's and 1's is not regular. | |
| Apr 10, 2016 at 20:17 | comment | added | Yuval Filmus | And what would the mistake be? | |
| Apr 10, 2016 at 20:16 | comment | added | Michael Wehar | Again, correct me if I'm wrong, but there might be a mistake on Wikipedia: en.m.wikipedia.org/wiki/Parikh%27s_theorem | |
| Apr 10, 2016 at 19:34 | comment | added | Yuval Filmus | That's right. So scrambling could make a language easier. | |
| Apr 10, 2016 at 19:22 | comment | added | Michael Wehar | Correct me if I am wrong, but it seems that you proved that if $L$ is context-free, then scramble($L$) is accepted by a non-deterministic one-counter automata. | |
| Apr 7, 2016 at 3:22 | vote | accept | Vim | ||
| Apr 6, 2016 at 19:57 | history | answered | Yuval Filmus | CC BY-SA 3.0 |