Given a regular language $L$ over $\Sigma:=\{1,2,3\}$, is $Sort(L)$ context-free?

Question

Given an ordered alphabet $\Sigma$, denote $Sort(w)$ the word obtained from $w$ when ordering the characters of $w$ ascending. For a language $L$, define $Sort(L):=\{Sort(w) | w \in L \}$.

Let $L$ be a regular language over $\Sigma:=\{1,2,3\}$. is $Sort(L)$ context-free?

I understand why it is important that $|\Sigma| \leq 2$ (otherwise, we can construct a counter-example using the pumping lemma), but I'm not sure about $\Sigma:=\{1,2,3\}$. Any clues?

Answer 1

Let $L$ be the regular language $(abc)^*$. Then $Sort(L) = \{a^nb^nc^n \mid n \geqslant 0 \}$ is not context-free.

Answer 2

Posting the answer as a reference for others:

Construct a CFG using a minor change (in bold) to the algorithm that turns a DFA into a CFG:

1. Make a variable $R_i$ for each state $q_i$ of the DFA.
2. Add the rule $R_i \rightarrow \sigma R_j$ to the CFG if there is a DFA transition with a character $\sigma \neq b$ from state Ri to Rj, and a rule $R_i \rightarrow R_j b$ to the CFG if there is a DFA transition with the character b.
3. Add the rule $R_i \rightarrow \epsilon$ if $q_i$ is an accept state.
4. Make $R_0$ the start variable - where $q_0$ is the start state of DFA.

This constructs a CFG for Sort(L). Hence, it is context-free.