# Deformation of finite regular languages [closed]

Let $L \subseteq \{0,1\}^n$ be any finite regular language s.t it has an acyclic DFA. Let $C$ be some class of acyclic DFAs.

Let $\sigma \in S_n$ be a permutation on $n$ symbols. We can apply $\sigma$ to a string $w$ of length $n$ by permuting symbols of $w$ according to $\sigma$ and we denote the new string by $\sigma(w)$.

Let $L(\sigma)=\{\sigma(w) \mid w \in L\}$.

What interesting classes $C$ one can define s.t for any finite regular language $L$, either $L$ has a DFA in the class $C$ (L is recognized by a DFA which satisfies properties of class C) or there is a permutation $\sigma$ such that $L(\sigma)$ has a DFA in the class $C$.

Effect of permutation, an example: $L =\{ww | w \in \{0,1\}^n\}$ has only acyclic DFA of size $\Omega(2^n)$ but there is a $\sigma$ such that $L(\sigma) =\{w_1^2w_2^2\cdots w_n^2 | w \in \{0,1\}^n\}$ has $O(n)$ size DFA. I refer $L(\sigma)$ as a deformation of $L$.

Is there some references for study of these kind? are similar questions for CFL studied?

Thank you.

• I'm confused. A finite automaton is supposed to accept any word in a language, reject the words not in a language, and the order does not matter. Maybe you meant something different? – András Salamon Sep 18 '17 at 20:39
• Sometimes order does matter. For eg, $w \in L$ but $w^r \notin L$. Also, I edited the question as I am looking for deformation w.r.t reordering. – Raj.R Sep 19 '17 at 5:09
• Can you define defomation more precisely? Must a deformation be a reordering of the characters in the strings? Are all reorderings allowed? Does $\mbox{sorted}(L)$ qualify? – reinierpost Sep 19 '17 at 7:38
• So you are interested in functions $f:\Sigma^*\to\Sigma^*$ such that for each symbol $a\in\Sigma$, the number of occurrences of $a$ is equal in $w$ and $f(w)$, i.e., $f$ permutes the symbols in $w$. And now you are looking for a function $f$ with this property, such that the minimal automaton for each regular language $L$ is significantly larger than a minimal automaton for $f(L)$? – Danny Sep 19 '17 at 7:42
• Also do you want to have a set of functions $f_L$ (so the function depends on the language), or are you interested in one function $f$ which is used for all regular languages? – Danny Sep 19 '17 at 7:48

1) Here is a paper that studies your question in the case of finite languages $L$, and shows that if a finite language $L$ can be decided by an $n$-state DFA, then any permutation of $L$ can be decided by an $m$-state DFA for some $m \leq \frac13 (n^2 + n + 1)$:
• Thank you for the reference. This paper studies state complexity of $L'=\{\sigma(w) \mid \sigma \in S_n \& w \in L\}$ where $L \subseteq \Sigma^n$ and L has a $\bf{chain}$ DFA and for general L where $L$ does not have a chain DFA, question (upper bound) is still open (end of sec. 1 in journal version). Also I am looking for the complexity of $L'(\sigma)=\{\sigma(w) \mid w \in L\}$ where $\sigma$ is fixed. Is it possible for any $L$ there is a permutation $\sigma$ which makes $L'(\sigma)$ is easy. – Raj.R Sep 20 '17 at 6:27