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

Chapter 2
Equations Over Languages and Finite Automata

2.1 Preliminaries on Languages and Finite Automata

2.1.1 Languages and Operators

Definition 2.1.1. An alphabet is a finite set of symbols. The set of all finite strings
over a fixed alphabet X is denoted by X ? . X ? includes the empty string . A subset
L X ? is called a language over alphabet X .

A language L over the alphabet X V is a language over the alphabet A Df .x; v / j
x 2 X; v 2 V g . Standard set-theoretic operations are defined on alphabets, e.g.,
union and intersection.
Some standard operations on languages are:

1. Given languages L 1 and L 2 , respectively over alphabets X 1 and X 2 , the language
L 1 [ L 2 over alphabet X 1 [ X 2 is the union of languages L 1 and L 2 .
2. Given languages L 1 and L 2 , respectively over alphabets X 1 and X 2 , the language
L 1 L 2

Df ˛ˇ j ˛ 2 L 1 ;ˇ 2 L 2 g over alphabet X 1 [ X 2 is the concatenation of

and L 2 .DefineL 0 Df g , L i D LL i 1 .The Kleene closure of L languages L 1

is the set L ? D[ i D 0 L i and the positive Kleene closure of L is L C D[ i D 1 L i .

i D 0 L i .
3. Given languages L 1 and L 2 , respectively over alphabets X 1 and X 2 , the language
L 1 \ L 2

Finally, the l -bounded Kleene closure of L is set L l

l

D[

over alphabet X 1 \ X 2 is the intersection of languages L 1 and L 2 .If

X 1 \ X 2 D; then L 1 \ L 2 D; .
4. Given a language L over alphabet X , the language L X ? n L over alphabet

X is the complement of language L. Similarly, given languages L 1

D

and L 2 ,

respectively over alphabets X 1 and X 2 , the language L 1 n L 2 D L 1 \ L 2 over

alphabet X 1 is the difference of languages L 1 and L 2 .
5. Given a language L over alphabet X , the language Pref .L/ Df x 2 X ? j9 y 2

X ? ;xy 2 L g is the prefix-closure of L, i.e., the language whose words are all
the prefixes of words in L.