Given L is a regular language, prove that Perm(L) is Context-Free

Question

Given a regular language $L$ defined over $\Sigma = \{0, 1\}$. We define a new language $$Perm(L) = \{w \mid \exists x \in L, w \in perm(x)\}, $$ where $perm(x)$ is the set of all permutations of the word $x$.

We have to show that $Perm(L)$ is context-free.

I have looked at the properties that neither CFL nor Regular languages are closed under permutation. Also, the problem comes with the following hint.

Hint: Build a PDA for $perm(L)$ which guesses a permutation of the input string and runs the DFA for $L$ on it, and uses the stack to check that it indeed guessed a valid permutation of the input string. The fact that the alphabet has only two symbols will be crucial for the latter check.

I am unable to use this hint to proceed further. Any help is appreciated!

Answer 1

For every symbol $\sigma_i$ that the PDA reads, it guesses a symbol $\tau_i$. It simulates the DFA on the word $\tau_1 \ldots \tau_i$, and will only accept if the DFA accepts. Using the stack, it maintains the following counter: $$ (\#_a(\sigma_1 \ldots \sigma_i) - \#_b(\sigma_1 \ldots \sigma_i)) - (\#_a(\tau_1 \ldots \tau_i) - \#_b(\tau_1 \ldots \tau_i)), $$ and only accepts if this equals zero at the end. Since $$ \#_a(\sigma_1 \ldots \sigma_i) + \#_b(\sigma_1 \ldots \sigma_i) = \#_a(\tau_1 \ldots \tau_i) + \#_b(\tau_1 \ldots \tau_i), $$ the counter equals zero iff $\tau_1 \ldots \tau_i$ is a permutation of $\sigma_1 \ldots \sigma_i$ (this only works because the alphabet is binary).

To see that this approach doesn't work for a ternary alphabet, it suffices to consider $$ \operatorname{Perm}((abc)^*) \cap a^*b^*c^* = \{ a^nb^nc^n : n \geq 0 \}. $$

Answer 2

Clearly we cannot keep both the number of $a$'s and the number of $b$'s on the stack, because what order should we use. The solution (I think) is to keep the difference of these numbers on the stack. Or better, the difference between the promised numbers in the DFA computation on word $x\in L$ that we guess, and those that are realised by the (permuted) word $w$ that we read. The stack is used to count this difference (and we must be able to store both positive and negative numbers).

In each step of the computation (i) we read a symbol $a$ from the tape and (ii) randomly follow a letter $b$ in the DFA for $L$. If these letters match then we comtinue. If these letters differ we increase or decrease the number of symbols on the stack: say we increase that number if $a=0$ and decrease if $a=1$. We accept if the simulated computation on the DFA ends in an accepting state ánd the stack is empty (or better represents the number zero).

PS. This might look different from Yuval's solution, but it basically the same.)