AskSia

Plus

n this task, you will design an FSM which will set a particular output U to 1 ea...

Mar 12, 2024

n this task, you will design an FSM which will set a particular output U to 1 each time 0110 is encountered in a stream of inputs. Inputs are specified one at a time, and are represented by the variable I. To illustrate, consider the following example, which shows different values of U and I over time, where each cell is separated by a clock tick: I 1 0 1 1 0 0 1 1 0 1 0 1 1 0 1 1 0 1 1 0 1 U 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 1 0 0 1 In the above example, it may appear that the output of U is delayed with respect to input I. That is, when the 1 is 0110 is encountered, it's not until the next clock tick that U is set to 1. This is actually expected behavior, as it reflects the fact that first the circuit reads 1, and then it moves into a state that reports U = 1. a. (10 pts) Draw the finite state machine diagram corresponding to this task. Pay particularly close attention to where transitions should go which move “backwards” in the FSM. That is, it is expected that you'll have transitions which go to previously observed states, and these transitions won't necessarily all return to the same state.

To design a finite state machine (FSM) that sets the output U to 1 each time the sequence 0110 is encountered in a stream of inputs, we can define the FSM formally using a 5-tuple (Q, Σ, δ, q0, F), where:

Q is a finite set of states

Σ is the input alphabet (in this case, Σ = {0, 1})

δ is the transition function: δ: Q × Σ → Q

q0 is the start state

F is the set of accept states (states where U=1)

For the FSM that detects the sequence 0110, we can define the states as follows:

q0: start state, no input read or sequence does not match

q1: state after reading '0'

q2: state after reading '01'

q3: state after reading '011'

q4: state after reading '0110' (accept state)

The transition function δ can be defined as:

δ(q0, 0) = q1

δ(q1, 1) = q2

δ(q2, 1) = q3

δ(q3, 0) = q4

δ(q4, 1) = q2 (since after 0110, if a 1 is read, the new sequence could be 01101)

δ(q4, 0) = q1 (since after 0110, if a 0 is read, the new sequence could be 01100)

δ(q1, 0) = q1 (stays in the same state if another 0 is read)

δ(q2, 0) = q1 (goes back to state q1 if a 0 is read)

δ(q3, 1) = q3 (stays in the same state if another 1 is read)

The accept state is q4, where U is set to 1.

Here is the LaTeX code to generate the graph of the state machine:

latex

Since the graph is simple and contains only 5 states, the LaTeX code provided should be sufficient to generate the graph. Please compile this code using a LaTeX editor to visualize the FSM.