Information Technology Reference
In-Depth Information
changes cause the rules of
G
to become the following. (Below we use a different numbering
scheme because all these rules replace rules
(
a
)
through
(
k
)
.)
1
)
→
7
)
→
13
)
→
(
E
+
T
(
E
)
(
E
T
2
)
→
∗
8
)
→
a
14
)
→
)
)
E
T
F
T
3
)
→
9
)
→
b
15
)
+
→
+
(
E
)
E
T
4
)
→
a
10
)
→
16
)
∗
→∗
(
E
)
E
F
5
)
→
b
11
)
→
a
E
F
6
)
→
∗
12
)
→
b
T
T
F
F
We now reduce the number of non-terminals on the right-hand side of each rule to two
through the addition of new non-terminals. The result is shown in Example
4.11.3
below,
where we have added the non-terminals
A
,
B
,
C
,
D
,
G
,and
H
.
EXAMPLE
4.11.3
Let
G
6
=(
N
6
,
T
6
,
R
6
,
E
)
(with start symbol
E
) be the grammar with
N
6
=
{
+
∗
(
)
}
T
6
=
{
a
,
b
,
+
,
∗
,
(
,
)
}
R
6
consisting of the rules given
A
,
B
,
C
,
D
,
E
,
F
,
G
,
H
,
T
,
,
,
,
,
,and
below.
(
A
)
→
(
I
)
→
(
Q
)
→
E
)
E
EA
T
TD
H
(
B
)
→
(
J
)
→
∗
(
R
)
→
a
+
T
A
D
F
F
(
C
)
→
(
K
)
→
(
S
)
→
b
(
G
E
TB
T
F
(
D
)
→
∗
(
L
)
→
(
T
)
→
(
E
)
(
B
F
G
(
E
)
→
(
M
)
→
a
(
U
)
→
)
(
C
)
E
T
(
F
)
→
(
N
)
→
b
(
V
)
→
+
E
)
+
C
T
(
G
)
→
a
(
P
)
→
(
W
)
∗
→∗
(
H
E
F
(
H
)
→
b
E
The new grammar clearly generates the same language as does the original grammar, but it
is in Chomsky normal form. It has 22 rules, 13 non-terminals, and six terminals whereas the
original grammar had seven rules, three non-terminals, and six terminals.
We now use the Chomsky normal form to show that for every CFL there is a polynomial-
time algorithm that tests for membership of a string in the language. This algorithm can be
practical for some languages.
THEOREM
4.11.2
Given a context-free grammar
G
=(
N
,
T
,
R
,
S
)
,an
O
(
n
3
2
)
-step algo-
|N|
∈T
∗
of length
n
is in
L
(
G
)
and to construct
rithm exists to determine whether or not a string
w
a parse tree for it if it exists.
Proof
If
G
is not in Chomsky normal form, convert it to this form. Given a string
w
=
(
w
1
,
w
2
,
...
,
w
n
)
, the goal is to determine whether or not
S
⇒
w
.Let
∅
denote the empty
set. The approach taken is to construct an
(
n
+
1
)
(
n
+
1
)
set matrix
S
whose entries
are sets of non-terminals of
G
with the property that the
i
,
j
entry,
a
i
,
j
,isthesetofnon-
terminals
C
such that
C
∗
×
⇒
w
i
···
w
j−
1
. Thus, the string
w
is in
L
(
G
)
if
S
∈
a
1,
n
+
1
,since
S
generates the entire string
w
. Clearly,
a
i
,
j
=
∅
for
j
≤
i
. We illustrate this construction
with the example following this proof.
We show by induction that set matrix
S
is the transitive closure (denoted
B
+
)ofthe
(
n
+
1
)
×
(
n
+
1
)
set matrix
B
whose
i
,
j
entry
b
i
,
j
=
∅
for
j
=
i
+
1when1
≤
i
≤
n
Search WWH ::
Custom Search