I have the following question which im not able to do. I have done things with DFA/NFA's before but this is the first time ive seen a question like this, I have been looking for similar questions in google but havent been able to find anything. Any help in how to complete the question would be appreciated.
Consider a finite state machine $Μ$ with 1-bit output. The output is given by the following logic equations. Show the state transition table of $M$ with the minimum number of states. In the following equations, $I(t)$ and $O(t)$ denote the values of the input and the output at time t, respectively.
- $O(0) = 0$
- $O(1) = I(0) \cdot I(1)$
- $O(t) = I(t) \cdot I(t-1) + I(t) \cdot I(t-2) + I(t-1) \cdot I(t-2), $where $ t \geq 2$
Interesting exercise. I will give a full answer later on, but here is a hint. The output of your machine can be computed as follows: given a sequence of bits $b_0b_1 \dotsm b_n$, add two $0$ in the front to get $00b_0b_1 \dotsm b_n$, then read this new sequence by blocks of three bits and output the majority of each block. Thus you output successively the majority of the blocks $00b_0$, $0b_0b_1$, $b_0b_1b_2$, $b_1b_2b_3$, etc. The majority of a block is $1$ if at least two bits are equal to $1$ and is $0$ otherwise. Now, a machine with $4$ states suffices to compute this function.
Update. Here is the sequential automaton:
Some details. The input is in red, the output in blue and the vertical bar is a separator. Next, if $b_t, b_{t-1}, b_{t-2}$ are bits, then $b_t⋅b_{t-1} + b_t⋅b_{t_2} + b_{t-1}⋅b_{t-2}$ is equal to the majority of $b_t, b_{t-1}, b_{t-2}$. The states represent the first two bits of a block of three and the transitions are given by $$\large (b_{t-2}b_{t-1}) \xrightarrow{\color{red}{b_t} \mid \color{blue}{MAJ(b_t, b_{t-1}, b_{t-2})}} (b_{t-1}b_t) $$