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

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?

• In general it is NOT True. For example consider $L$ itself to be sorted. $L=\{a^nb^nc^n\}$ then by Bar-Hillel Lemma, it is not-context free. – SaeidAli May 19 '17 at 13:11
• But in this case $L$ itself is not regular. What about when $L$ is regular? – mibarg May 20 '17 at 6:29
• Sorry, I did not consider $L$ to be regular. Nice answer. – SaeidAli May 23 '17 at 11:25

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.