This is an old revision of the document!

Closure properties of finite state machines

If we have some number of finite state machines, we show how to create a finite state machine whose language is union, intersection, complement, concatenation, or iteration of the languages of these state machines.

Complement

Let $A = (\Sigma,Q,\Delta,q_0,F)$ . Let $\lnot A = (\Sigma,Q,\Delta,q_0,Q \setminus F)$ . Then $L(\lnot A) = \Sigma^* \setminus L(A)$ .
This is only true if A is a deterministic FSM. If A is nondeterministic, we must first convert it into an equivalent deterministic FSM, then take the complement. This can result in an exponential blowup of the number of states.

Union

Put two machines together disjointly, with a new initial state that has epsilon transitions to the original initial states. Let $A = (\Sigma, Q_A, q_0^A, \Delta_A, F_A)$ and $B = (\Sigma, Q_B, q_0^B, \Delta_B, F_B)$ .
Then the union of the two automata will be $C=(\Sigma, Q_A \cup Q_B, q_0, \Delta_A \cup \Delta_B \cup \{(q_0,\epsilon, q_0^A), (q_0,\epsilon, q_0^B)\}, F_A \cup F_B)$ .

Intersection

Product of state spaces, even for non-deterministic machines.

Concatenation

Put one machine after another, with epsilon transitions from the accepting states of the first machine to the start state of the second machine.
The new accepting states are those of the second machine.

Iteration (Kleene star)

Create a new initial state which is accepting and has an epsilon transition to the old start state.
Put a loop around the existing machine by adding epsilon transitions from the accepting states to the new start state.

Comments

Deterministic versus non-deterministic machines in input and output.

Cost of complementation. Cost of determinization.