How to merge two finite state automata?
algorithm, deterministic, finite-automata, state-machine
Solution
The textbooks usually gives the automaton `C` such that `L(C) = L(A) U L(B)` by applying de-morgan on it, L(C) = (L(A)C [intersection] L(B)C)C. The intersection is done by building the Cartesian product automaton, and the negation is simply switching the accepting states. Building the union automaton can also be done directly: Build the Cartesian product automaton, and a final state is a state `(a,b)` such that `a` is a final state in the automaton of `A` OR `b` is a final state in the automaton of `B`
An alternative is building a Non-Deterministic Final Automaton (NFA) by simply creating a new state, and add an epsilon path for both start(A) and start(B), and use the standard algorithm for eliminating non-determinism from an automaton.
The problem - this automaton will not be minimal (far from it probably). You can try and use this algorithm on the resulting automaton in order to minimze it.
Problem
Say I have two deterministic finite state automata represented by the following transition diagrams: FSA for keyword IF: IF ``` ___ ___ _ / \ I / \ F // \\ >| 0 |----->| 1 |----->||2|| \___/ \___/ \\_// ``` FSA for an ID: [A-Z][A-Z0-9]* ``` ------------ ___ | _ LET | / \ LET // \\<------ >| 0 |----->||1|| \___/ \\_//<------ | NUM | ------------ ``` What algorithm may I use to combine them into a single deterministic finite state automata with three final states, represented by the following transition diagram: ``` ----------------------- | LETTER BUT F OR NUM | -------- ___ | _ _ LET v _ | LET | / \ I // \\ F // \\----->// \\<------ >| 0 |----->||1||----->||2|| ||3||<-------- \___/ \\_// \\_//----->\\_//<------ | | NUM | NUM | | | ANY LETTER OTHER THAN I ------------ | --------------------------------------------- 1: ID 2: IF (IT'S ALSO AN ID, BUT THE KEYWORD IF HAS A HIGHER PRECEDENCE) 3: ID ```