Equations Over Languages and Finite Automata - The Unknown Component Problem: Theory and Applications - page 20

builds the DFA F 0 Dh 2 S ;˙;ı;r;Q 0 i , where (1) the states s 2 2 S are the subsets
of S , (2) the transition relation is ı.i; s/ D[ s 2 s f s 0 j .i;s;s 0 / 2 g and (3) a state is
final, i.e., s 2 Q 0 2 S ,iffs \ Q ¤; . Since many of the states in 2 S are unreachable
from the initial state, they can be deleted and so the determinized automaton usually
has fewer states than the power set. 4 To make a NDFA complete it is not necessary to
apply the full-blown subset construction, but it suffices to add a new non-accepting
state s d whose incoming transitions are .i;s;s d / for all i; s for which there was
no transition in the original automaton. By a closure construction [63], an NDFA
with -moves can be converted to an NDFA without -moves; however, a subset
construction must be applied at the end to determinize it.
The equivalence of regular expressions and finite automata is shown by matching
each operation on regular expressions with a constructive procedure that yields the
finite automaton of the result, given the finite automata of the operands. For the most
common operations (union, concatenation, complementation, intersection) see [63].
Here we sketch the constructions for the less known operations of projection, lifting,
restriction and expansion:
projection ( # )GivenFAF that accepts language L over X V ,FAF 0 that accepts
language L # V over X is obtained from F by the following procedure:
replace each edge ..x; v /; s; s 0 / by the edge .x;s;s 0 /.
lifting ( " )GivenFAF that accepts language L over X ,FAF 0 that accepts
language L " V over X V is obtained from F by the following procedure:
replace each edge .x;s;s 0 / by the edges ..x; v /; s; s 0 /; 8 v 2 V .
restriction ( + )GivenFAF that accepts language L over X [ V ,FAF 0 that accepts
language L + V over V is obtained from F by the following procedure:
8 x 2 X n V , change every edge .x;s;s 0 / into the edge .;s;s 0 /, i.e., replace
the symbols x 2 X n V by . 5
expansion ( * )GivenFAF that accepts language L over X ,FAF 0 that accepts
language L * V over X [ V (X \ V D; ) is obtained from F by the following

procedure:

for each state s, 8 v 2 V add the edge (self-loop) . v ;s;s/.
l -expansion ( * l )GivenFAF that accepts language L over X ,FAF 0 that accepts
language L * .V;l/ , l integer, over X [ V (X \ V D; ) is obtained from F by the

following procedure:
1. The set of states S 0 of F 0 is given by

S 0 D S [f .s; j / j s 2 S; 1 j

l g :

4 It is not uncommon in practice to find that j S jj S j .
5 Apply the closure construction to obtain an equivalent deterministic finite automaton without
-moves.