Hardware Reference
In-Depth Information
The
largest solution
is a solution that contains any other solution. B
D;
is the
trivial solution.
Theo
rem 2.
16.
The largest solution of the equation
A
˘
X
C
is the language
S
D
A
˘
C
.
If
A
˘
A
˘
C
D
S
then
A
˘
C
is the largest solution of the equation
A
˘
X
D
C
.
Proof.
Consider a string ˛
2
.U
[
O/
?
,then˛ is in the largest solution of A
˘
X
C iff A
˘f
˛
g
C and the following chain of equivalences follows:
A
˘f
˛
g
C
,
.A
*
O
\f
˛
g
*
I
/
+
I
[
O
\
C
D;,
by
Prop
:2:1.c/C
D
.C
*
U
/
+
I
[
O
.A
*
O
\f
˛
g
*
I
/
+
I
[
O
\
.C
*
U
/
+
I
[
O
D;,
by
Prop
:2:5.d/
since
..C
*
U
/
+
I
[
O
/
*
U
D
C
*
U
.A
*
O
\f
˛
g
*
I
\
C
*
U
/
+
I
[
O
D;,
by
Prop
:2:7.d/
A
*
O
\f
˛
g
*
I
\
C
*
U
D;,
by
Prop
:2:7.d/
.A
*
O
\f
˛
g
*
I
\
C
*
U
/
+
U
[
O
D;,
by
Prop
:2:5.d/
since
f
˛
g
*
I
D
..
f
˛
g
*
I
/
+
U
[
O
/
*
I
.
f
˛
g
*
I
/
+
U
[
O
\
.A
*
O
\
C
*
U
/
+
U
[
O
D; ,
by
Prop
:2:1.c/.
f
˛
g
*
I
/
+
U
[
O
Df
˛
g
f
˛
g\
.A
*
O
\
C
*
U
/
+
U
[
O
D; ,
˛
62
.A
*
O
\
C
*
U
/
+
U
[
O
,
˛
2
.A
*
O
\
C
*
U
/
+
U
[
O
,
˛
2
A
˘
C
Therefore the largest solution of the language equation A
˘
X
C is given by the
language
S
D
A
˘
C:
(2.6)
t
Corolla
ry 2.17
.
A language
B
over alphabet
U
[
O
is a solution of
A
˘
X
C
A
˘
C
.
iff
B
Proposition 2.18.
If
S
is
U
-convergent, then
S
is the largest
U
-convergent solution
of the equation, and a language
B
¤;
is a
U
-convergent solution iff
B
S
.
When S is not U -convergent the largest U -convergent solution does not exist, since
any finite subset of S is a U -convergent solution and therefore no string can be
deleted from S without missing a solution. An analogous proposition and remark
hold for S -compositionally U -convergent solutions.
Search WWH ::
Custom Search