Information Technology Reference
In-Depth Information
and
b
i
,
i
+
1
is defined as follows:
b
i
,
i
+
1
=
{
|
(
A
→
w
i
)
in
R
where
w
i
∈T}
A
⎡
⎣
⎤
⎦
∅
b
1,2
∅
...
∅
∅∅
b
2,3
...
∅
.
.
.
.
.
.
.
B
=
∅∅ ∅
...
b
n
,
n
+
1
∅∅ ∅
...
∅
Thus, the entry
b
i
,
i
+
1
is the set of non-terminals that generate the
i
th terminal symbol
w
i
of
w
in one step. The value of each entry in the matrix
B
is the empty set except for the
entries
b
i
,
i
+
1
for 1
.
We extend the concept of matrix multiplication (see Chapter
6
)totheproductoftwo
set matrices. Doing this requires a new definition for the product of two sets (entries in the
matrix) as well as for the addition of two sets. The
product
S
1
≤
i
≤
n
,
n
=
|
w
|
·
S
2
of sets of nonterminals
S
1
and
S
2
is defined as:
S
1
·
S
2
=
{
|
there exists
B
∈
S
1
and
C
∈
S
2
such that
(
A
→
BC
)
∈R}
A
Thus,
S
1
·
S
2
is the set of non-terminals for which there is a rule in
R
of the form
A
→
BC
where
B
S
2
.The
sum
of two sets is their union.
The
i
,
j
entry of the product
C
=
D
∈
S
1
and
C
∈
m
matrices
D
and
E
,each
containing sets of non-terminals, is defined below in terms of the product and union of sets:
×
E
of two
m
×
m
c
i
,
j
=
d
i
,
k
·
e
k
,
j
k
=
1
We also define the
transitive closure
C
+
of an
m
×
m
matrix
C
as follows:
C
+
=
C
(
1
)
C
(
2
)
C
(
3
)
C
(
m
)
∪
∪
∪···
where
s
−
1
C
(
s
)
=
C
(
r
)
C
(
s−r
)
and
C
(
1
)
=
C
×
r
=
1
By the definition of the matrix product, the entry
b
(
2
)
=
i
+
2
and otherwise is the set of non-terminals
A
that produce
w
i
w
i
+
1
through a derivation tree
of depth 2; that is, there are rules such that
A
i
,
j
of the matrix
B
(
2
)
is
∅
if
j
→
→
w
i
,and
C
→
w
i
+
1
,which
BC
,
B
implies that
A
∗
w
i
w
i
+
1
.
Similarly, it follows that both
B
(
1
)
B
(
2
)
and
B
(
2
)
B
(
1
)
are
⇒
∅
in all positions except
i
,
i
+
3
2. The entry in position
i
,
i
+
3of
B
(
3
)
=
B
(
1
)
B
(
2
)
B
(
2
)
B
(
1
)
contains the set of non-terminals
A
that produce
w
i
w
i
+
1
w
i
+
2
through a derivation tree of
depth 3; that is,
A
for 1
≤
i
≤
n
−
→
BC
and either
B
produces
w
i
w
i
+
1
through a derivation of depth 2
(
B
⇒
w
i
w
i
+
1
)and
C
produces
w
i
+
2
in one step (
C
→
w
i
+
2
)or
B
produces
w
i
in one step
w
i
)and
C
produces
w
i
+
1
w
i
+
2
through a derivation of depth 2 (
C
∗
(
B
→
⇒
w
i
+
1
w
i
+
2
).
Search WWH ::
Custom Search