Another interesting property of DFAs is that they can be combined. This allows more complex problems to be solved by creating smaller and easier DFAs and then combining them together to solve the entire problem. For example a DFA that checks to see if a string of s and s has at least two s and three s can be created by combining the DFA () that checks to see if a string has at least two s and the DFA () that checks to see if the string has at least three s.
The set of states of this new DFA () are the cross product of the internal states of and . A state is the initial state of if both of its components were initial states of and , and a state is the final state of if both of its components were final states of and .
The transition function of is defined as follows . As a result this gives us the DFA transition table and diagram:
Notice is the initial state of because is the initial states of both and . is the final state of because is the final state of and is the final state of .
- What is a Finite State Machine?
- Deterministic Finite Automata
- Examples of DFA part 1
- Examples of DFA part 2
- Examples of DFA part 3
- Combining DFAs
- Limits and Languages of DFAs
- Automata Theory, Languages, and Computation by John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman