How to combine two automata with a final state?

Question

Let's say I have two deterministic finite state automata represented by the following transition diagrams:

FSA for the keyword IF: IF

___ ___ _ / \ I / \ F // \\ >| 0 |----->| 1 |----->||2|| \___/ \___/ \\_// 

FSA for identifier: [AZ] [A-Z0-9] *

  ------------ ___ | _ LET | / \ LET // \\<------ >| 0 |----->||1|| \___/ \\_//<------ | NUM | ------------ 

Which algorithm can I use to combine them into one deterministic finite state machine 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 ALSO AN ID, BUT THE KEYWORD IF HAS A HIGHER PRECEDENCE) 3: ID 

Answer 1

Textbooks usually give an automaton C such that L(C) = L(A) UL(B) , applying de-morgan on it, L (C) = (L (A) ^C [intersection] L (B) ^C ) ^C .
The intersection is carried out by constructing the Cartesian automaton of the product, and negation simply switches the receiving states.
Creating a combined automaton can also be done directly: construct the Cartesian product of automata, and the final state is state (a,b) such that a is the final state in the automaton a OR b is the final state in the automaton b

An alternative is to create a Non-Definistic Final Automaton (NFA) by simply creating a new state and adding the epsilon path to start (A) and start (B), and use the standard algorithm for eliminating non-determinism from the machine.

The problem is that this machine will not be minimal (perhaps far from it). You can try to use this algorithm on the resulting machine to minimize it.