Do a system model in terms of: States, Inputs, Outputs, Next state (state transi
ID: 2247698 • Letter: D
Question
Do a system model in terms of: States, Inputs, Outputs, Next state (state transition) function, and Readout (output) function. Define the states, inputs and outputs in terms of a description and as formal mathematical sets. Define next state function in terms of description and as a state transition diagram or a mathematical function or pseudo code, define time scale for your model. Pattern Recognizer (using a state transition diagram) Consider a Pattern Recognizer that accepts single digit inputs (0 or a 1) each time unit and outputs a NO (as a 0) until the pattern 101101 has been in the stream of inputs then a YES (as a 1) will be output. Consider a register that hold the last several digits received and shifts in a new digit when received and shifts out the oldest digit.
Explanation / Answer
the pattern has to be a, b, c, a, b, c, a, b, c, . . ..
It uses the states 0, 1, and 2 to stand for the situations in which it is expecting an a, b, and c,
respectively; and it uses state 3 for the situation in which it has seen an input that was not the one
that was expected. Once the machine goes to state 3 (sometimes called a rejecting state), it never
exits that state.
S = {0, 1, 2, 3}
I = {a, b, c}
O = {true, false}
1 if s = 0, i = a
2 if s = 1, i = b
n(s, i) =0 if s = 2, i = c
3 otherwise
false if n(s, i) = 3
o(s, i) =
true otherwise
s0 = 0
State transition diagram for language acceptor.
We will use tables like the following one to examine the evolution of a state machine:
time 0 1 2 ...
input i0 i1 i2 ...
state s0 s1 s2 ...
output o1 o2 o3 ...
For each column in the table, given the current input value and state we can use the output
function o to determine the output in that column; and we use the n function applied to that
input and state value to determine the state in the next column. Thus, just knowing the input
sequence and s0, and the next-state and output functions of the machine will allow you to fill in
the rest of the table.
For example, here is the state of the machine at the initial time point:
time 0 1 2 ...
input
state
output
i0
s0
...
...
...
Using our knowledge of the next state function n, we have: time 0 1 2 ... input i0 ... state s0 s1 ... output ... and using our knowledge of the output function o, we have at the next input value time 0 1 2 ... input i0 i1 ... state s0 s1 ... output o1 ... This completes one cycle of the statement machine, and we can now repeat the process. Here is a table showing what the language acceptor machine does with input sequence (’a’, ’b’, ’c’, ’a’, ’c’, ’a’, ’b’): time 0 1 2 3 4 5 6 7 input state output ’a’ 0 True ’b’ 1 True ’c’ 2 True ’a’ 0 True ’c’ 1 False ’a’ 3 False ’b’ 3 False 3 The output sequence is (True, True, True, True, False, False, False).
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.