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?

  • $\begingroup$ 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. $\endgroup$ – SaeidAli May 19 '17 at 13:11
  • $\begingroup$ But in this case $L$ itself is not regular. What about when $L$ is regular? $\endgroup$ – mibarg May 20 '17 at 6:29
  • $\begingroup$ Sorry, I did not consider $L$ to be regular. Nice answer. $\endgroup$ – SaeidAli May 23 '17 at 11:25

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.


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.