2
$\begingroup$

Let $Q= \{q_1,\ldots,q_n\}$ be a set of permutations of some finite set $X$. Let $Q' = \{q \in Q^* \mid q=1\in S_X\}$, where $S_X$ is the symmetric group on $X$. Is $Q'$ a regular language?

1 Answers 1

3

Construct a graph $\Gamma$ having as vertices the elements of the symmetric group $S(X)$, and for each $g\in S(X)$ and each $i\in\{1,\dots,n\}$ an arrow from the vertex $g$ to the vertex $q_ig$ labeled $q_i$. Upgrade $\Gamma$ into a deterministic automatic so that the initial state is the identity element $e$ of $S(X)$, and the only accepted state is $e$ itself.

What is the language accepted by the automaton $\Gamma$?