Question

Construct a finite-state automaton with four states that recognizes the set of bit strings containing an even number of 1s and an odd number of 0s.

Short answer

The result is

State	0	1
\({{\bf{s}}_{\bf{0}}}\)	\({{\bf{s}}_{\bf{2}}}\)	\({{\bf{s}}_{\bf{1}}}\)
\({{\bf{s}}_{\bf{1}}}\)	\({{\bf{s}}_{\bf{3}}}\)	\({{\bf{s}}_{\bf{0}}}\)
\({{\bf{s}}_{\bf{2}}}\)	\({{\bf{s}}_{\bf{0}}}\)	\({{\bf{s}}_{\bf{3}}}\)
\({{\bf{s}}_{\bf{3}}}\)	\({{\bf{s}}_{\bf{1}}}\)	\({{\bf{s}}_{\bf{2}}}\)

Step-by-step solution

Construction of deterministic finite-state automaton.

Let us consider four states \({{\bf{s}}_{\bf{0}}}{\bf{,}}{{\bf{s}}_{{\bf{1,}}}}{{\bf{s}}_{\bf{2}}}{\bf{,}}{{\bf{s}}_{\bf{3}}}\).

Let start with the state be \({{\bf{s}}_{\bf{0}}}\).Since the empty string is not the set S and is not a final state.

The state \({{\bf{s}}_{\bf{0}}}\) has that there were an even number of 0’s and 1’s in the previous digit.

The state \({{\bf{s}}_{\bf{1}}}\) shows that there were an even number of 0’s and an odd number of 1’s in the previous digits.

The state \({{\bf{s}}_{\bf{2}}}\) has the odd numbers of 0’s and an even number of 1’s in the previous digits.

The state \({{\bf{s}}_{\bf{3}}}\) gives that an odd number of 0’s and an odd number of 1’s in the previous digits.

It moves from \({{\bf{s}}_{\bf{0}}}\) to \({{\bf{s}}_{\bf{1}}}\), if the input is a 1 and moves from \({{\bf{s}}_{\bf{0}}}\) to\({{\bf{s}}_{\bf{2}}}\) if the input is a 0.

It moves from \({{\bf{s}}_{\bf{1}}}\) to \({{\bf{s}}_{\bf{0}}}\), if the input is 1 and move from \({{\bf{s}}_{\bf{1}}}\)to\({{\bf{s}}_{\bf{3}}}\) if the input is a 0.

It moves from \({{\bf{s}}_{\bf{2}}}\) to \({{\bf{s}}_{\bf{3}}}\), if the input is 1 and move from\({{\bf{s}}_{\bf{2}}}\) to\({{\bf{s}}_{\bf{0}}}\)if the input is a 0.

It moves from \({{\bf{s}}_{\bf{3}}}\) to \({{\bf{s}}_{\bf{2}}}\), if the input is 1 and moves from\({{\bf{s}}_{\bf{3}}}\)to \({{\bf{s}}_{\bf{1}}}\)if the input is a 0.

If the input is 1, then it remains at the current state.

Sketch of deterministic finite-state automaton.

The sketch of deterministic finite-state automation can be drawn by four states \({{\bf{s}}_{\bf{0}}}{\bf{,}}{{\bf{s}}_{\bf{1}}}{\bf{,}}{{\bf{s}}_{\bf{2}}}{\bf{,}}{{\bf{s}}_{\bf{3}}}\). The sketch is

Other way of representing in tabular form.

State	0	1
\({{\bf{s}}_{\bf{0}}}\)	\({{\bf{s}}_{\bf{2}}}\)	\({{\bf{s}}_{\bf{1}}}\)
\({{\bf{s}}_{\bf{1}}}\)	\({{\bf{s}}_{\bf{3}}}\)	\({{\bf{s}}_{\bf{0}}}\)
\({{\bf{s}}_{\bf{2}}}\)	\({{\bf{s}}_{\bf{0}}}\)	\({{\bf{s}}_{\bf{3}}}\)
\({{\bf{s}}_{\bf{3}}}\)	\({{\bf{s}}_{\bf{1}}}\)	\({{\bf{s}}_{\bf{2}}}\)

Therefore, this is the require construction.