6
$\begingroup$

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.

$\endgroup$
5
  • 2
    $\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, 2016 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, 2016 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, 2016 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, 2016 at 19:21
  • $\begingroup$ This is also proved in a note by Dexter Kozen: cs.cornell.edu/~kozen/papers/2and3.pdf. $\endgroup$ May 15, 2016 at 19:56

2 Answers 2

9
$\begingroup$

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.

$\endgroup$
11
  • 1
    $\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$ Apr 10, 2016 at 19:22
  • $\begingroup$ That's right. So scrambling could make a language easier. $\endgroup$ Apr 10, 2016 at 19:34
  • 1
    $\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$ Apr 10, 2016 at 20:19
  • 1
    $\begingroup$ 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. $\endgroup$ Apr 10, 2016 at 20:23
  • 1
    $\begingroup$ 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? $\endgroup$ Apr 10, 2016 at 20:26
4
$\begingroup$

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$.

$\endgroup$
3
  • 3
    $\begingroup$ "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… $\endgroup$
    – Nathaniel
    Mar 2 at 14:33
  • $\begingroup$ Thanks for the edit! It was much needed. $\endgroup$
    – Nathaniel
    Mar 3 at 12:26
  • $\begingroup$ 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.) $\endgroup$ Mar 3 at 23:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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