Cryptography Reference
In-Depth Information
went bungee-jumping
where2
0
1
went shooting
where
went flying
where
went bungee-jumping in Minnesota.
went bungee-jumping in Kalamazoo.
0
1
0
1
0
1
verb
0
1
went fishing
where
in Minnesota.
in Timbuktu.
in Kathmandu.
in Kalamazoo.
0
1
in Timbuktu.
in Kathmandu.
0
1
0
1
where2
where
0
1
Figure 7.6: A Huffman tree that converts bits into productions for the
variable
verb
,
where
and
where2
from Table 7.3.3.
Bits
before
Bits
after
Phrase
Contractions
Contractions
Laverne and Shirley went bungee-jumping
101100
101011
in Minnesota.
Laverne and Shirley went bungee-jumping
101101
1010000
in Timbuktu.
Fred and Barney went shooting
0001
01111
in Kalamazoo.
Fred and Barney went bungee-jumping
1100100
1100100
in Minnesota.
Thelma and Louise went bungee-jumping
010000
010000
in Minnesota.
Some of the relationships among the noun, verb, and location are
still preserved, but some aspects are significantly changed. A series
of expansions and contractions can scramble any grammar enough
to destroy any of these relationships.
Athirdnewvariable,
who
, was also introduced through contrac-
tion, but it created a production that was not in Greibach Normal
Form (
noun
who
went fishing
where
).
This would not work with the parser used to generate Figure
7.1. The grammar is still not ambiguous. This example was only
included to show that the expansions and contractions can work
around grammars that are not in Greibach Normal Form.
One interesting question is the order in which the bits are applied
to the production in this case. The previous examples in Greibach
→
