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

6. Given a language L over alphabet X , L Pref

is the largest prefix-closed

language L 0 with L 0 L.

It is useful to recall the notions of substitution and homomorphism of lan-
guages [63]. A substitution f is a mapping of an alphabet X onto subsets of Y ? for
some alphabet Y . The substitution f is extended to strings by setting f./ Df g
and f.xa/ D f.x/f.a/.An homomorphism h is a substitution such that h.a/ is
a singleton string for each symbol a in the alphabet X . We introduce some useful
operations on languages. The first two are associated with synchronous composition,
while the last two are associated with parallel composition. These operations are
integral parts of constructing the most general solution.

1. Given a language L over alphabet X V , consider the homomorphism p W X
V

! V ? defined as

p..x; v // D v ;

then the language

L # V Df p.˛/ j ˛ 2 L g

over alphabet V is the projection of language L to alphabet V ,orV -projection
of L. By definition of substitution p./ D .
2. Given a language L over alphabet X and an alphabet V , consider the substitution
l ! 2 .X V/ ? W X defined as

l.x/ Df .x; v / j v 2 V g ;

then the language

L " V Df l.˛/ j ˛ 2 L g

over alphabet X V is the lifting of language L to alphabet V ,orV -lifting of
L. By definition of substitution l./ Df g .
3. Given a language L over alphabet X [ V , consider the homomorphism r

W X [

! V ? defined as

V

y if y

2 V

r.y/ D ;

if y 2 X n V

then the language

L + V Df r.˛/ j ˛ 2 L g

over alphabet V is the restriction of language L to alphabet V ,orV -restriction
of L,i.e.,wordsinL + V are obtained from those in L by deleting all the symbols
in X that are not in V . By definition of substitution r./ D .
4. Given a language L over alphabet X and an alphabet V , consider the mapping
e W X

! 2 .X [ V/ ? defined as

n X/ ? e.x/ Df ˛xˇ j ˛; ˇ 2 .V g ;