Sea Σ el conjunto de todas las biyecciones de {1, …, 5} a {1, …, 5}, donde id denota la función identidad, es decir, id(j) = j,∀j. Sea ° la composición de funciones. Para una string x = x 1 x 2 … x n ∈ Σn, n ≥ 0, sea π(x) = x 1 °x 2 ° … °x n .
Considere el lenguaje L = {x ∈ Σ* ⏐ π(x) = id}. El número mínimo de estados en cualquier DFA que acepta L es _________ .
Nota: Esta fue una pregunta de tipo numérico.
(A) 120
(B) 125
(C) 210
(D) Ninguno de estos
Respuesta: (A)
Explicación: ¡El DFA para aceptar L tendrá 5! = 120 estados, ya que necesitamos un estado para cada función de permutación posible en 5 elementos.
Entonces, la respuesta es 120 .
Cuestionario de esta pregunta
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA