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} \cdots x_{n} \in \sum n_{p} n \geq 0, let (x)=x_{1} \circ x_{2} \circ . . . \circ x_{n} . Consider the language L=\{x \in \sum * ∣(x)=i d\}. The minimum number of states in any DFA accepting {L} is _________.

GATE Computer Science (CS) 2019 Solved Papers

Question : 58 of 65

Marks: +1, -0

Let

Σ

be the set of all bijections from

\{1, . . ., 5\}

\{1, . . ., 5\}

, where id denotes the identity function, i.e.

{id}(j)=j, ∀ j .

Let

∘

denote composition on functions. For a string

x=x_{1} x_{2} ⋅s x_{n} ∈ Σ n_{p} n ≥ 0

, let

(x)=x_{1} ∘

x_{2} ∘ . . . ∘ x_{n} .

Consider the language

L=\{x ∈ Σ * ∣(x)=i d\}

. The minimum number of states in any DFA accepting

{L}

is _________.

Your Answer:

Validate

Solution:

The DFA for accepting L will have 5! = 120 states, since we need one state for every possible permutation function on 5 elements. The starting state will be “id” state, named as

(\table 12345 ; 12345)

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 π(x) = id only the starting state (“id” state) will be the final state. Sample machine with only 2 states is shown below

Go to Question:

Prev Question

Next Question