Lab for Automated Reasoning and Analysis LARA

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.


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.


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)$.


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


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.


If we start with deterministic machines, for which of the above constructions will we get a deterministic machine as a result?

What is the cost of computing the machine for the complement of the language?

closure_properties_of_finite_state_machines.txt · Last modified: 2008/09/17 09:19 by vkuncak