Example: Examples of DFA

(related to Chapter: Finite Automata (Finite Sequential Machines))

Example 1

This DFA accepts words over the alphabet $\{0,1,2,3,4,5,6,7,8,9\}$ and decides whether or not they denote a positive integer divisible by $5$.

dfa3

For instance, the input word $19403$ will lead to the states $abbbab$, and the end state $b$ shows that $19403$ is not divisible by $5$. The input word $925$ will lead to the states $abba$, and the end state $a$ shows that $925$ is divisible by $5$.

Example 2

This DFA accepts words over the alphabet $\{0,1\}$ with exactly two $1$'s.

dfa2

If a string has more than two $1$'s, the DFA will enter the state $d$ which is not demarked as final.

Example 3

This DFA accepts words from the alphabet $\{0,1\}$ containing an even number of $1$'s.

dfa4

Examples: 1 2


Thank you to the contributors under CC BY-SA 4.0!

Github:
bookofproofs


References

Bibliography

  1. Erk, Katrin; Priese, Lutz: "Theoretische Informatik", Springer Verlag, 2000, 2nd Edition
  2. Hoffmann, Dirk: "Theoretische Informatik, 3. Auflage", Hanser, 2015