Proving that the scramble of a regular language is context-free

Question

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.

Answer 1

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.

Answer 2

We can prove this without using Parikh's theorem. Assume that a language $L$ over the two-letter alphabet $\{0,1\}$ is given by a finite-state machine. For the language $\mathrm{SCRAMBLE}(L)$ we construct an automaton with one register capable of holding any integer (positive or negative). The states are the same as in the finite-state machine. Transitions that read $1$s are simply copied to the automaton. Transitions that read $0$s are replaced by transitions that decrease the register. In addition, at each state we add a loop transition that reads a $0$ from the input tape and increases the register. This one-register automaton accepts the language $\mathrm{SCRAMBLE}(L)$ if we require the register to contain zero at the end. Indeed, let $w \in L$ and $t \in \mathrm{SCRAMBLE}(w)$. In order to accept the word $t$, our non-deterministic automaton guesses the word $w$ and follows the same sequence of states as the original finite-state machine that reads $w$. During this process the integer register keeps track of surplus $0$s seen in the word $t$ (this number can be negative).

Finally, we convert this automaton with one integer register to an ordinary pushdown automaton with two stack symbols, one of them used for representing positive values of the register, the other one for negative values. These two stack symbols are $A$ and $B$; they play the same role as the stack symbols "zero" and "negative zero" in Yuval Filmus's answer. We require the stack to be empty at the end. It can be shown that this pushdown automaton recognizes the language $\mathrm{SCRAMBLE}(L)$.

A direct formal construction follows. Here we skip the intermediate step with the one-register automaton and go straight to the final PDA. We are going to use the definition of a PDA without initial stack symbol and with the following acceptance mode: an input string is accepted at a configuration if the complete input string has been read, the stack is empty, and the PDA is in one of its accepting states.

Suppose $L$ is recognized by a non-deterministic finite automaton, which is a tuple $M=(Q,\Sigma,\delta,q_0,F)$, where $Q$ is a finite set, $\Sigma = \{0,1\}$, $\delta$ is a function from $Q \times \Sigma$ to $\mathcal{P}(Q)$, $q_0 \in Q$, and $F \subseteq Q$. If we follow the above construction, then for $\mathrm{SCRAMBLE}(L)$ we obtain the PDA $M'=(Q,\Sigma,\Gamma,\delta',q_0,F)$, where $\Gamma = \{A,B\}$ and \begin{align*} \delta'={}&\{(p,\epsilon,\epsilon,q,\epsilon) \mid q \in \delta(p,\epsilon)\}\\ &\cup\{(p,1,\epsilon,q,\epsilon) \mid q \in \delta(p,1)\}\\ &\cup\{(p,\epsilon,A,q,\epsilon) \mid q \in \delta(p,0)\}\\ &\cup\{(p,\epsilon,\epsilon,q,B) \mid q \in \delta(p,0)\}\\ &\cup\{(p,0,B,p,\epsilon) \mid p \in Q\}\\ &\cup\{(p,0,\epsilon,p,A) \mid p \in Q\}. \end{align*} We define a function $\mathrm{unary}:\mathbb{Z}\to\Gamma^*$ by putting $\mathrm{unary}(n)=A^n$ for non-negative $n$ and $\mathrm{unary}(n)=B^{-n}$ for negative $n$. For example, $\mathrm{unary}(2)=AA$ and $\mathrm{unary}(-2)=BB$. One can prove that if $|w|_1=|t|_1$ and $(q_0,w)\vdash_M^*(q,\epsilon)$, then $(q_0,t,\epsilon)\vdash_{M'}^*(q,\epsilon,\mathrm{unary}(|t|_0-|w|_0))$. (We use induction on the number of steps plus $|t|_0$.) Thus, if $M$ accepts $w$, $|w|_1=|t|_1$, and $|w|_0=|t|_0$, then $M'$ accepts $t$.

On the other hand, by induction on the number of steps one can prove that if $(q_0,t,\epsilon)\vdash_{M'}^*(q,\epsilon,\gamma)$, then there exists a word $w$ such that $|w|_1=|t|_1$, $|t|_0-|w|_0 = |\gamma|_A-|\gamma|_B$, and $(q_0,w)\vdash_M^*(q,\epsilon)$. Thus, if $M'$ accepts $t$, then $M$ accepts $w$ for some $w$ satisfying $|w|_1=|t|_1$ and $|w|_0=|t|_0$.