ISRO | CS ISRO 2014 | Pregunta 2 – Part 6

¿El número de estados requeridos por una Máquina de Estados Finitos, para simular el comportamiento de una computadora con una memoria capaz de almacenar ‘m’ palabras, cada una de ‘n’ bits de longitud es?
(A) mx 2 ⁿ
(B) 2 ^m+n
(C) 2 ^mn
(D) m+n

Respuesta: (C)
Explicación: dadas, ‘m’ palabras, cada una de ‘n’ bits de longitud, por lo que el número total de bits = m*n
Un estado de autómatas de estado finito puede almacenar 1 bit de datos, y un estado puede tener 0 o 1.
Por lo tanto, el número total de estados requeridos por una máquina de estado finito = 2 ^mn .

Entonces, la opción (C) es correcta.
Cuestionario de esta pregunta