Earlier we discussed set operations for languages generated by regular grammars. More precisely, I showed that the union of two such languages is such a language, but I didn’t answer the question for intersections or relative complements. For languages recognised by finite state automata I’ll answer the question for intersections and relative complements, but not for unions. It’s actually fairly easy to answer the question for unions as well, but it’s unnecessary, as we’ll see later.
To construct a finite state automaton for the intersection of two languages from finite state automata for each language individually we just need to keep track of what states those two automata could be in at any point. To be more precise, suppose the two automata have the same set of tokens \({ A }\) and have sets of states \({ S _ 1 }\) and \({ S _ 2 }\), sets of initial states \({ I _ 1 }\) and \({ I _ 2 }\), sets of accepting states \({ F _ 1 }\) and \({ F _ 2 }\), and transition relations \({ T _ 1 }\) and \({ T _ 2 }\). We construct a finite state automaton with the same set of tokens \({ A }\), a set of states \({ S }\), a set of initial states \({ I }\), a set of accepting states \({ F }\) and a transition relation \({ T }\) which recognises those lists which are recognised by both these automata as follows.
At every point in the input this automaton can be in the state \({ ( s _ 1 , s _ 2 ) }\) if and only if the first automaton can be in the state \({ s _ 1 }\) and second can be in the state \({ s _ 2 }\). It therefore can reach an accepting state at the end of the input if and only if both the original automata could.
So the intersection of two languages recognised by finite state automata is a language recognised by a finite state automaton.
It might seem obvious how to modify this construction for relative complements. We just need to replace accepting states by rejecting for one of the automata, right? This isn’t completely wrong, but it’s not completely right either. For one thing, it’s possible for a finite state automaton to halt unsuccessfully before reaching the end of its input, if there are no allowed transitions for the symbol just read from the current state. For another, the fact that a non-deterministic automaton can end up in a rejecting state at the end of the input doesn’t mean the input must be rejected, since some other set of choices for the initial state or transitions might leave it in an accepting state. Neither of these things can happen though if the finite state automaton is one which was constructed by the power set construction though, since those are always strongly deterministic, so if we first apply the power set construction to our finite automata and then the naive version of the relative complement construction described earlier it will work.
So the relative complement of two languages recognised by finite state automata is a language recognised by a finite state automaton.