 The Eduladder is a community of students, teachers, and programmers just interested to make you pass any exams. So we help you to solve your academic and programming questions fast.
Watch related videos of your favorite subject.
Connect with students from different parts of the world.
See Our team
Wondering how we keep quality?
Got unsolved questions?

GATE-CS-2019-->View question

## Let Σ be the set of all bijections from {1, ... , 5} to {1, ... , 5}, where id denotes the identity function, i.e. id(j) = j, ∀j. Let ∘ denote composition on functions. For a string x = x1 x2 ⋯ xn ∈ Σ n , n ≥ 0 , let π(x) = x1 ∘ x2 ∘ ⋯ ∘ xn. Consider the language L = {x ∈ Σ ∗ | π(x) = id }. The minimum number of states in any DFA accepting L is .

Let Σ be the set of all bijections from {1, ... , 5} to {1, ... , 5}, where id denotes the identity
function, i.e. id(j) = j, ∀j. Let ∘ denote composition on functions. For a string x =x1 x2 ⋯ xn ∈ Σn, n ≥ 0 , let π(x) = x1 ∘ x2 ∘ ⋯ ∘ xn.
Consider the language L = {x ∈ Σ∗| π(x) = id }. The minimum number of states in any DFA accepting L is .

Taged users:

Likes:
Be first to like this question

Dislikes:
Be first to dislike this question