# If a language L is regular then the given operation sort(L) is context free

I was asked in one of my homework tasks this next question and I'm not quite sure how to handle it:

Sort(w) is an operation which takes a string (w) from a given language and sorts the characters in an ascending order. Sort(L) is the outcome language of the operation Sort(w) on each and every string (w) in the language L. I was asked to prove or disprove the following claim:

If L is a regular language over the alphabet {0,1} where 0<1 then sort(L) is context free.

I would appreciate any hints or clues on how to approach this type of question.

## 1 Answer

The way to solve this sort of question is using your problem-solving skills. Here are three ways to approach this question:

• Take some DFA (or NFA) for $L$. Now construct a PDA for $\mathsf{sort}(L)$ along the following lines. The PDA starts by reading $0$s, pushing them into the stack. At some point it switches to a second phase in which it only accepts $1$s. At each step it first pops an arbitrary number of $0$s from the stack and feeds them to the DFA, and then reads the next $1$ if any, feeding it to the DFA. It accepts if after processing all the $0$s in the stack and all the $1$s in the input, the DFA is in an accepting state.

• Take a left regular grammar for $L$ (so the rules are of the form $A\to\epsilon$, $A\to a$, and $A\to a B$), and replace $A\to 1B$ with $A\to B1$. The result is a context-free grammar for $\mathsf{sort}(L)$.

• Parikh's theorem states that $\mathsf{sort}(L)$ is of the form $$\bigcup_{i=0}^m \{ 0^{x_i+n_1 y_{i,1}+\cdots+n_{\ell_i} y_{i,\ell_i}} 1^{z_i + n_1 w_{i,1} + \cdots + n_{\ell_i} w_{i,\ell_i}} : n_1,\ldots,n_{\ell_i} \geq 0 \},$$ where $x_i,y_{i,j},z_i,w_{i,j} \geq 0$. It's not hard to check that all languages of this form are context-free, for example by constructing a context-free grammar.

Note how all of these approaches rely on the alphabet being binary. The language $(012)^*$ shows that this assumption is necessary. (Similarly, the language $(01)^*$ shows that $\mathsf{sort}(L)$ need not be regular.)

Parikh's theorem implies that for languages over the binary alphabet, $\mathsf{sort}(L)$ is context-free whenever $L$ is context-free (that is, we don't need to assume that $L$ is regular, it suffices to assume that it is context-free). You can try proving this fact directly.

• Your second suggestion is by far the simplest. – Thumbnail May 19 '17 at 13:22
• Hey! thanks for the answer! I have one question though, what do you mean by "a left regular grammar"? – Lola May 20 '17 at 5:03
• Sorry again for the bothering, but could you please add a diagram to the first option? I'm trying to 'see' how it works :) – Lola May 20 '17 at 5:53
• I explained what a left regular grammar is in the answer. A language has such a grammar iff it is regular. Regarding your other question, drawing automata is out of the scope of this answer. – Yuval Filmus May 20 '17 at 5:56