Timeline for Proving that the scramble of a regular language is context-free
Current License: CC BY-SA 4.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 3 at 23:40 | comment | added | Hendrik Jan | An alternative construction was proposed by Yuval , simulating the FSA and scramble-PDA in parallel, keeping the difference of the numbers of 0/1 and 1/0 mismatches on stack. (Scramble is called permutation. That question was later than this one, the answer came earlier. I feel ilke a confused time traveller.) | |
| Mar 3 at 12:26 | comment | added | Nathaniel | Thanks for the edit! It was much needed. | |
| Mar 3 at 11:50 | history | edited | Mati | CC BY-SA 4.0 |
Added a formal construction and a proof scheme.
|
| Mar 2 at 14:33 | comment | added | Nathaniel | "This one-register automaton accepts the language $\text{SCRAMBLE}(L)$ if we require the register to contain zero at the end." Could you please elaborate? This does not seem obvious… | |
| Mar 2 at 14:09 | review | Late answers | |||
| Mar 9 at 13:55 | |||||
| S Mar 2 at 13:49 | review | First answers | |||
| Mar 3 at 12:33 | |||||
| S Mar 2 at 13:49 | history | answered | Mati | CC BY-SA 4.0 |