# Examples of DFA Part 1

Here are a few examples of DFAs. The Finite state machine that accepts all strings of $1$s and $0$s that have at least two $0$s. The input is $\{0,1 \}$ since the string only consists of $1$s and $0$s. The set of states is $\{A,B,C \}$ because it will only require three states to count two $0$s. The transition function is defined as:

The automata will take in a string of $1$s and $0$s such as $0101$ one character at a time. First $\delta(A, 0) = B$, then $\delta(B, 1) = B$, then $\delta(B,0) = C$, and finally $\delta(C,1) = C$ which is a final state, therefore this DFA accepts the string 0101.

However if the automata is fed the string $1011$ there will be an entirely different result. First $\delta(A, 1) = A$, then $\delta(A,0) = B$, then $\delta(B,1) = B$, and finally $\delta(B,1) = B$. However $B$ is not a final state, therefore this DFA rejects the string $1011$.

Filed Under: Crash Courses, Computer Science

Sources Used

• Automata Theory, Languages, and Computation by John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman