Question

Let $\sum$ be the set of all bijections from $\{1,.....,5\}$ to $\{1,.....,5\}$. where id denotes the identity function, i.e. id(j) = j, $\forall j$. Let $\circ$ denote composition on functions.

For a string $x=x_1{x}_2...x_nϵ{\sum }^n,n\ge 0,let\pi \left(x\right)=x_1\circ x_2\circ ....\circ x_n$

Consider the language L = $\{xϵ{\sum }^{\ast }\mid \pi (x)=id\}$ The minimum number of states in any DFA accepting L is

• A. 2

Answer 1

The correct option is A 2
The DFA for accepting L will have 5! = 120 states, since we need one state for every possible permutation function on 5 elements. The statrting state will be "id" state, named as $\left(\begin{array}{c}12345\\ 12345\end{array}\right)$ and from there n! arrows will go the n! states each named with a distinct permutation of the set {1, 2, 3, 4, 5}. Since composition of permutation function is closed every arrow has to go to some permutation and hence some state.

Since the language only has those strings where $\pi \left(x\right)=id$ only the starting state ("id" state) will be the final state. Sample machine with only 2 states is shown below