I need to show that there exists a polynomial time algorithm that inputs a deterministic automata $A$, and decides if $A$ accepts a word w if and only if it also accepts any word obtained by permuting the letters of w.
Would appreciate any help.
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this communityI need to show that there exists a polynomial time algorithm that inputs a deterministic automata $A$, and decides if $A$ accepts a word w if and only if it also accepts any word obtained by permuting the letters of w.
Would appreciate any help.
A language $L$ is said to be commutative if the following property holds:
for every word $a_1 \dotsm a_n \in L$ and any permutation $\sigma$ on $\{1, \ldots, n\}$, the word $a_{\sigma(1)} \dotsm a_{\sigma(n)}$ is also in $L$.
Now, my understanding of your question is the following:
given a finite deterministic automaton $\mathcal{A}= (Q, A, \cdot)$, decide whether the language accepted by $\mathcal{A}$ is a commutative language.
There is a polynomial algorithm to answer this question. Indeed a language is commutative if and only if its syntactic monoid is commutative. But the syntactic monoid $M(L)$ of $L$ is equal to the transition monoid of its minimal automaton. It follows that, $L$ is commutative if and only if the generators of $M(L)$ commute. In terms of automata, this is equivalent to check, for every pair of letters $(a, b)$, whether $q \cdot ab = q \cdot ba$ for all $q \in Q$.
Now, given $\mathcal{A}$, you can compute the minimal automaton of $L$ in $O(|Q|\log |Q|)$ and then check commutativity in $O(|Q||A|^2)$.