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

( ( ) If the string ˛ 1 u 1 :::˛ k u k ˛ k C 1 2 L 1 \ L 2

* I , then it holds that * I

˛ 1 u 1 :::˛ k u k ˛ k C 1 2 L 1 and ˛ 1 u 1 :::˛ k u k ˛ k C 1 2 L 2

* I ; thus u 1 ::: u k

2 L 1 ,

* I

u 1 ::: u k 2 L 2 , implying u 1 ::: u k 2 L 1 \ L 2 , and so it is also ˛ 1 u 1 :::˛ k u k ˛ k C 1 2

.L 1 \ L 2 / * I .
Similarly one proves the first and third identity involving [ .
Thesis: if M 2 D .M 2

+ U / * I

(or M 1 D .M 1

+ U / * I )then.M 1

\ M 2 / + U D

M 1 + U \ M 2 + U .
( ) )Ifthestring u 1 ::: u k 2 .M 1 \ M 2 / + U then there exists ˛ 1 ;:::˛ k ;˛ k C 1 2 I ?
such that it holds that the string ˛ 1 u 1 :::˛ k u k ˛ k C 1

2 M 1 \ M 2 , i.e., ˛ 1 u 1 :::˛ k u k

˛ k C 1 2 M 1 , ˛ 1 u 1 :::˛ k u k ˛ k C 1 2 M 2 ,andso u 1 ::: u k 2 M 1 and u 1 ::: u k 2

+ U

M 2 + U .
( ( ) If the string u 1 ::: u k 2 M 1 \ M 2

+ U , i.e., u 1 ::: u k

2 M 1 and

+ U + U

I ? u 1 ::: u k 2 M 2

+ U , then there exists ˛ 1 :::˛ k ˛ k C 1

2 such that ˛ 1 u 1 :::˛ k u k

˛ k C 1 2 M 1 . Moreover, since M 2 D .M 2

+ U / * I , from u 1 ::: u k

2 M 2 it

+ U

follows that ˛ 1 u 1 :::˛ k u k ˛ k C 1 2 M 2 . In summary, ˛ 1 u 1 :::˛ k u k ˛ k C 1 2 M 1 and

˛ 1 u 1 :::˛ k u k ˛ k C 1 2 M 2 , implying ˛ 1 u 1 :::˛ k u k ˛ k C 1 2 M 1 \ M 2 , from which

follows u 1 ::: u k 2 .M 1 \ M 2 / + U . t

Example 2.6. The identity .M 1 \ M 2 / + U D M 1 + U \ M 2 + U does not hold without
the additional hypothesis in Prop. 2.5 (d). Consider I Df a; b g , U Df u g , M 1 D
f a u g , M 2 Df b u g ,then.M 1 \ M 2 / + U D; + U D; and M 1 + U \ M 2 + U D
f u g\f u gDf u g . Notice that a u and b u are words of length 2 on the alphabet I [ U .

Proposition 2.7. The following equivalences hold.

(a) Let L be a language over alphabet I ,then L " O D;, L D;
(b) Let L be a language over alphabet I O ,then L # O D;, L D; In the next
two statements, suppose that I and O are disjoint alphabets.
(c) Let L be a language over alphabet I

[ O ,then L * O D;, L D;

(d) Let L be a language over alphabet I [ O ,then L + O D;, L D; .

Proof. The proofs are straightforward; implication ) of statement (d) is true
because, even in the case that all strings in L are defined only over symbols
from alphabet I , their restriction to alphabet O yields the empty string (i.e.,
2 L + O ¤; ) and so from L ¤; follows that L + O ¤; . t

2.1.2 Finite Automata and Regular Expressions

Definition 2.1.2. A finite automaton (FA) is a 5-tuple F Dh S; ˙; ; r; Q i .
S represents the finite state space, ˙ represents the finite alphabet, and
˙ S S is the next state relation, such that .i;p;n/ 2 iff n 2 S is a next
state of present state p 2 S on symbol i 2 ˙ . The initial or reset state is r 2 S and
Q S is the set of final or accepting states. A variant of FAs allows the introduction
of -moves, meaning that .˙ [f / g S S .