Examples of DFA Part 1

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

automata1
Notice that the arrow denotes which state is the starting state and the star represents the final state.

The automata will take in a string of 1s and 0s 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.

finite1
The transition diagram of the DFA. The arrow pointing to A shows that A is the initial state, the double circle around C represents that C is a final state. The 1s and 0s above the arrows show which transition will be taken with that input.

Previous | Next

  1. What is a Finite State Machine?
  2. Deterministic Finite Automata
  3. Examples of DFA part 1
  4. Examples of DFA part 2
  5. Examples of DFA part 3
  6. Combining DFAs
  7. Limits and Languages of DFAs
  8. Applications

Filed Under: Crash Courses, Computer Science

Sources Used

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

Sharing the Wonder