# finite-state automata

## Construct a deterministic finite-state automaton that recognizes the set of all bit strings that contain exactly three 0s.

We will follow a similar approach to previous exercises to solve this exercise. Let’s define 5 states as follows: S0, the initial state S1 is the state when the automata read exactly one 0 S2 is the state when the automata read exactly two 0s S3 is the state when the automata read exactly three […]

## Construct a deterministic finite-state automaton that recognizes the set of all bit strings that do not contain three consecutive 0s.

We will follow a similar approach to previous exercises to solve this exercise. Let’s define 4 states as follows: S0, the initial state S1 is the state when the automata read a 0 S2 is the state when the automata read a sequence of two 0s S3 is the state when the automata read a

## Construct a deterministic finite-state automaton that recognizes the set of all bit strings that contain the string 101

We will follow a similar approach to previous exercises to solve this exercise. Let’s define 4 states as follows: S0, the initial state S1 is the state when the automata read a 1 S2 is the state when the automata read a 0 after a 1 S3 is the state when the automata read a

## Construct a deterministic finite-state automaton that recognizes the set of all bit strings that end with 10

This exercise is a bit more difficult than the previous one. To solve this exercise, let’s use the following strategy: define states in which the automaton can be if it just reads a 1 or a 0. – We can have a state S1 which means the automaton read 0s. Therefore, from the state S0

## Construct a deterministic finite-state automaton that recognizes the set of all bit strings beginning with 01

To solve this exercise, we have to options. We can answer using a state table or state diagram. First, we need to consider that to be in the final state, we need first to start from S0, and recognize a 0, and then a 1. This tells us that we should have at least three