For strings $w$ and $t$, if they have the same length and comprise the same characters (namely, they are two permutations of these characters), then $w\sim t$. For a string $w$, define an operator $\operatorname {SCRAMBLE}$ such that $$\operatorname {SCRAMBLE}(w):=\{t\mid t\sim w\}, $$ and for a language $A$, $$\operatorname {SCRAMBLE}(A):=\{t\mid t\sim w, \exists w\in A\}.$$ Prove that: given an alphabet $\Sigma:=\{0,1\}$, for any regular language $L$, $\operatorname {SCRAMBLE}(L)$ is a context-free language.

I have tried to use the pumping lemma of regular language to show that it satisfies the pumping lemma of context-free language after the $\operatorname {SCRAMBLE}$ operation, but I failed to find the pumping substring of $\operatorname {SCRAMBLE}(L)$. I have also tried PDA construction but to no avail. Can anyone help me with it? Any answer or hint will be appreciated. Thanks in advance.

  • 1
    $\begingroup$ You can not use the Pumping lemma in this way; non-context-free languages can fulfill its conditions. You need to show that there is a CFG or NPDA (or...) for that language. $\endgroup$ – Raphael Apr 5 '16 at 17:05
  • $\begingroup$ In the definition of $\operatorname {SCRAMBLE}(A)$, the quantifier $\exists w$ should probably go before the statement $t \sim w$. $\endgroup$ – DylanSp Apr 5 '16 at 17:15
  • $\begingroup$ @Raphael but it seems hard for me to construct a CFG or NPDA... So do you have any suggestion about it? $\endgroup$ – Vim Apr 5 '16 at 23:40
  • $\begingroup$ Thanks, @YuvalFilmus -- this has been re-opened. Vim, may I encourage you to edit the question based on the feedback and comments you've received? $\endgroup$ – D.W. Apr 6 '16 at 19:21
  • $\begingroup$ This is also proved in a note by Dexter Kozen: cs.cornell.edu/~kozen/papers/2and3.pdf. $\endgroup$ – Yuval Filmus May 15 '16 at 19:56

First, two remarks. When $L = (01)^*$, we have $\newcommand{\scramble}{\mathrm{SCRAMBLE}}\scramble(L) \cap 0^*1^* = \{ 0^n 1^n : n \geq 0 \}$, and this shows that we can't expect $\scramble(L)$ to be regular.

Second, when $L=(012)^*$, we have $\scramble(L) \cap 0^*1^*2^* = \{ 0^n 1^n 2^n : n \geq 0 \}$. This shows that it's important that the alphabet have only two symbols.

Now for the proof. It is actually enough to assume that $L$ is context-free (and not necessarily regular). For a word $w$, let $p(w) = (\#_0(w),\#_1(w))$, and define $P(L) = \{ p(w) : w \in L \}$. Parikh's theorem states that $P(L)$ is a semilinear set, that is, a finite union of sets of the form $$ x + \sum_{i=1}^m \mathbb{N} y_i, $$ where $x,y_1,\ldots,y_m \in \mathbb{N}^2$. It is thus enough to show that for every linear set $S$, the language $L(S)$ of words $w$ such that $p(w)$ belongs to $S$ is context-free.

A pushdown automaton accepting $L(S)$ proceeds as follows. We will assume for simplicity that $x = (0,0)$; for general $x = (x_0,x_1)$, the PDA will ignore the first $x_0$ zeroes and $x_1$ ones, but will only accept if these actually appear.

When the PDA starts running, it guesses a mode $i \in \{1,\ldots,m\}$. When it reads $0$, it pushes it to the stack. Meanwhile, it keeps track of the number of $1$s it has read. Once it has read $(y_i)_1$ of them, it removes $(y_i)_0$ zeroes from the stack (pushing, if necessary, "negative" $0$s which will get cancelled later with actual $0$s). Then it guesses another mode $i \in \{1,\ldots,m\}$ (possibly the same one).

Upon reaching the end of input, the automaton verifies that it hasn't read any $1$s in its current phase, and that the stack is empty. This completes the construction. We leave it to the reader to prove that it actually works.

| cite | improve this answer | |
  • $\begingroup$ 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. $\endgroup$ – Michael Wehar Apr 10 '16 at 19:22
  • $\begingroup$ That's right. So scrambling could make a language easier. $\endgroup$ – Yuval Filmus Apr 10 '16 at 19:34
  • $\begingroup$ Again, correct me if I'm wrong, but there might be a mistake on Wikipedia: en.m.wikipedia.org/wiki/Parikh%27s_theorem $\endgroup$ – Michael Wehar Apr 10 '16 at 20:16
  • $\begingroup$ And what would the mistake be? $\endgroup$ – Yuval Filmus Apr 10 '16 at 20:17
  • $\begingroup$ 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. $\endgroup$ – Michael Wehar Apr 10 '16 at 20:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.