Home » Theory of Computation » Theory of computation miscellaneous » Question

Theory of computation miscellaneous

Theory of Computation

  1. Given the following state table of an FSM with two states A and B, one input and one output

    If the initial state is A = 0, B = 0, what is the minimum length of an input string, which will take the machine to the state A = 0, B = 1 with output = 1?
    1. 3
    2. 4
    3. 5
    4. 6
Correct Option: A

The initial state = 00
Final state required = 01
Let us construct the transition diagram for the given.

We get the total number of states to be 3 when getting the desired output. The transition diagram can further be elaborated as below.
There can be 4 states 00, 01, 10, 11.
With this, the FSM can be designed as

The desired output is obtained with the input string 101, however, the concern is number of states which we found to be 3.



Your comments will be displayed only after manual approval.