Information Technology Reference
In-Depth Information
αβγ
. Clearly the strings generated by the new rules are the same as are generated
by the old rules.
Let
A
→
and
A
1 be a rule in
G
where
w
i
∈
→
w
1
···
w
i
···
w
k
for some
k
≥
V
.Wereplace
k
.Here
Z
i
is a
new non-terminal. Clearly, the new version of
G
generates the same language as does
G
.
With these changes the rules of
G
consist of rules either of the form
A
→
Z
1
Z
2
···
Z
k
,and
Z
i
→
w
i
for 1
≤
i
≤
this rule with the new rules
A
→
u
,
u
∈T
+
(a string of at least one non-terminal). There are
→
w
,
w
∈N
(a single terminal) or
A
+
to consider, a)
two cases of
w
∈N
|
w
|
=
1andb)
|
w
|≥
2. We begin by eliminating all
→
rules of the first kind, that is of the form
A
B
.
B
can be cascaded to form rules of the type
C
⇒
→
Rules of the form
A
D
.Thenumber
!
because if any derivation contains two
instances of a non-terminal, the derivation can be shortened. Thus, we need only consider
derivations in which each non-terminal occurs at most once. For each such pair
C
,
D
with
a relation of this kind, add the rule
C
|N|
of distinct derivations of this kind is at most
D
to
G
.If
C
→
→
→
w
for
|
w
|≥
D
and
D
2or
w
=
u
∈T
,add
C
→
w
to the set of rules. After adding all such rules, delete all rules of
the form
A
B
. By construction this new set of rules generates the same language as the
original set of rules but eliminates all rules of the first kind.
We now replace rules of the type
A
→
→
···
A
k
,
k
≥
3.
Introduce
k
−
2new
A
1
A
2
non-terminals
N
1
,
N
2
,
···
,
N
k−
2
peculiar to this rule and replace the rule with the following
rules:
A
A
k−
1
A
k
. Clearly, the
new grammar generates the same language as the original grammar and is in the Chomsky
normal form.
→
A
1
N
1
,
N
1
→
A
2
N
2
,
···
,
N
k−
3
→
A
k−
2
N
k−
2
,
N
k−
2
→
EXAMPLE
4.11.2
Let
G
5
=(
N
5
,
T
5
,
R
5
,
E
)
(with start symbol
E
) be the grammar with
N
5
=
{
E
,
T
,
F
}
,
T
5
=
{
a
,
b
,
+
,
∗
,
(
,
)
}
,and
R
5
consisting of the rules given below:
a
)
→
E
+
T
d
)
→
f
)
→
a
E
T
F
F
b
)
→
e
)
→
(
E
)
g
)
→
b
E
T
F
F
c
)
→
∗
T
T
F
Here
E
,
T
,and
F
denote expressions, terms, and factors. It is straightforward to show that
E
⇒
(
a
∗
(
a
+
b
)
and
E
∗
b
+
a
)
∗
⇒
a
∗
b
+
a
are two possible derivations.
We convert this grammar to the Chomsky normal form using the method described in the
proof of Theorem
4.11.1
.Since
R
contains no
-rules, we do not need the rule
E
→
,nor
do we need to eliminate
-rules.
First we convert rules of the form
A
w
so that each entry in
w
is a non-terminal. To
do this we introduce the non-terminals
(
,
)
,
+
,and
→
∗
and the rules below. Here we use a
boldface font to distinguish between the non-terminal and terminal equivalents of these four
mathematical symbols. Since we are adding to the original set of rules, we number them
consecutively with the original rules.
h
)
→
j
)
→
(
(
+
+
∗
→∗
Next we add rules of the form
C
i
)
→
)
k
)
)
→
D
for all chains of single non-terminals such that
C
∗
D
. Since by inspection
E
∗
⇒
⇒
F
,weaddtherule
E
→
F
. For every rule of the form
A
→
B
for which
B
→
w
, we add the rule
A
→
w
. We then delete all rules of the form
A
→
B
.These
Search WWH ::
Custom Search