About permutation automaton and the properties of the group whose language is recognized

210 Views Asked by At

Given a permutation automaton (or pure-group automaton), its transition monoid is a finite permutation group K and its language is a group language (say of a group G). Is it known whether there is a connection between K and the properties of the group G? More precisely, given K, can we say something on the group G? I would be happy to get some reference on that topic.

1

There are 1 best solutions below

1
On

Let $L$ be a regular language of $A^*$ and let $\mathcal{A}$ be its minimal automaton. Then the transition monoid $K$ of $\mathcal{A}$ is the syntactic monoid of $L$. If $\mathcal{A}$ is a permutation automaton, then $K$ is a permutation group.

Now, if a finite group $G$ recognizes $L$, then there exists by definition a monoid morphism $f:A^* \to G$ and a subset $P$ of $G$ such that $L = f^{-1}(P)$. Then $H = f(A^*)$ is as subgroup of $G$ (of course $G = H$ if you assume $f$ to be surjective) and $K$ is a quotient of the group $H$. Possible reference: Chapter 4, Section 4 of this link.