Cryptography Reference
In-Depth Information
3. Create the productions
A
k
→ γ
i
for each
i
.
4. Delete the productions
V → β
1
γ
i
β
2
for each
i
and replace them
with one production,
V → β
1
A
k
β
2
.
Notice that all possible productions don't have to be contracted.
This can shorten the grammar significantly if it is applied success-
fully.
The expansion and contraction operations are powerful. If two
grammars,
G
2
, generate the same language, then there is
some combination of expansions and contractions that will convert
G
1
into
G
1
and
G
2
. This is easy to see because the expansion operation can
be repeated until there is nothing left to expand. The entire grammar
consists of a start symbol and a production that takes the start sym-
bol into a sentence from the language. It is all one variable and one
production for every sentence in the language. There is a list of ex-
pansions that will convert both
G
2
into the same language.
This list of expansions can be reversed by a set of contractions that
inverts them. So to convert
G
1
and
G
1
and
then apply the set of contractions that are the inverse of the expan-
sions that expand
G
1
into
G
2
, simply fully expand
. This proof will probably never be used in prac-
tice because the full expansion of a grammar can be quite large.
The most important effect of expansion and contraction is how it
rearranges the relationships among the bits being encoded and the
structure of the sentences. Here's a sample grammar:
G
2
noun
→
Bob and Ray
verb
Fred and Barney
verb
Laverne and Shirley
verb
Thelma and Louise
verb
verb
→
went fishing
where
went shooting
where
went bungee-jumping
where
went flying
where
where
→
in Minnesota.
in Timbuktu.
in Katmandu.
in Kalamazoo.
Each of these variables comes with four choices. If they're weighted
equally, thenwe can encode two bits with each choice. Number them
00, 01, 10, and 11 in order. So hiding the bits 110100 produces the
sentence “Thelma and Louise went shooting in Minnesota.”
Figure 7.5 shows a way
to convert 12 phrases
into bits.
There is also a pattern here. Hiding the bits 010100 produces the
sentence “Fred and Barney went shooting in Minnesota.” The first
two bits are directly related to the noun of the sentence, the second
two bits to the verb, and the third two bits depend on the location.
Most people who create a grammar follow a similar pattern because
