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.


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.

| cite | improve this answer | |
  • $\begingroup$ Your second suggestion is by far the simplest. $\endgroup$ – Thumbnail May 19 '17 at 13:22
  • $\begingroup$ Hey! thanks for the answer! I have one question though, what do you mean by "a left regular grammar"? $\endgroup$ – Lola May 20 '17 at 5:03
  • $\begingroup$ Sorry again for the bothering, but could you please add a diagram to the first option? I'm trying to 'see' how it works :) $\endgroup$ – Lola May 20 '17 at 5:53
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus May 20 '17 at 5:56

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.