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

then the language

L * V Df e.˛/ j ˛ 2 L g

over alphabet X [ V is the expansion of language L to alphabet V ,or
V -expansion of L, i.e., words in L * V are obtained from those in L by inserting

n X/ ? . Notice that e is not a substitution and

anywhere in them words from .V

n X/ ? that e./ Df ˛ j ˛ 2 .V g .

Given a language L over alphabet X , an alphabet V , and a natural number l ,
consider the mapping e l ! 2 .X [ V/ l W X defined as

n X/ l

e l .x/ Df ˛xˇ j ˛; ˇ 2 .V g ;

then the language

L * .V;l/ Df e l .˛/ j ˛ 2 L g

over alphabet X [ V is the l -bounded expansion of language L over alphabet
V ,or.V; l/-expansion of L, i.e., words in L * V are obtained from those in L

n X/ l . Notice that e l

by inserting anywhere in them words from .V is not a

n X/ l substitution and that e l ./ Df ˛ j ˛ 2 .V g .

By definition ; # V D; , ; " V D; , ; + V D; , ; * V D; , ; * .V;l/ D; .
The four previous operators change a language and its alphabet of definition;
in particular the operators " and # change what components are present in
the Cartesian product that defines the language alphabet. We assume that each
component has a fixed position in the Cartesian product. For instance, let language
L 1 be defined over alphabet I and language L 2 be defined over alphabet O,then
language L 1 " O is defined over alphabet I O and also language L 2 " I is defined
over alphabet I O, if by assumption I precedes O in the Cartesian product. More
precisely, say that we introduce an ordering of alphabets, i ,bywhichI is mapped
to index i.I/ and O is mapped to i.O/,theni.I/ < i.O/ implies that I precedes
O in any Cartesian product of alphabets. The ordering is arbitrary, but, once chosen,
it holds through the sequence of language operations.
The following straightforward facts hold between the projection and lifting
operators, and between the restriction and expansion operators.

Proposition 2.1. The following inverse laws for " ; # and * ; + hold.

(a) Let X and Y be alphabets, and let L be a language over alphabet X ,then
.L " Y / # X D L .
(b) Let X and Y be alphabets, and let L be a language over alphabet X Y ,then
.L # X / " Y L .
(c) Let X and Y be disjoint alphabets, and let L be a language over alphabet X ,
then .L * Y / + X D L .
(d) Let X and Y be disjoint alphabets, and let L be a language over alphabet
X [ Y ,then .L + X / * Y

L .