Cryptography Reference
In-Depth Information
This grammar will not increase the size of the file when it is en-
coded. Each variable has 256 different productions available to it, so
8 bits are consumed in the process of making the choice. The result
is one new terminal added to the stream which takes 8 bits to store.
There are potential problems with this system. The biggest one
is ensuring that the average string of terminals in the language is fi-
nite. If there are too many variables on the right-hand side of the
productions, then the generating process could never end. The stack
of pending variables would continue to grow with each production.
The solution is to make sure that the average number of variables on
the right-hand side of the production is less than one. The relation-
ship between the average number of variables and the average length
of the phrases in the language defined by the grammar is direct.
Asmallernumberofaveragevariablesmeansshorterphrases. As
the average number of variables approaches one, the average length
tends toward infinity.
3
The average length of a phrase in the language is not as important
in this particular example. The bits can be recovered easily here
because the grammar is in Greibach Normal Form and there is no
need to place parsing decisions on hold. Each terminal only appears
on the right hand side of one production per variable, so the final file
does not need to be a complete phrase produced by the grammar.
It could just be a partial one. There is no reason why the grammars
need to be as easy to parse, but more complicated grammars need to
have the entire phrase produced from the starting symbol.
7.4 Summary
This chapter has described simple ways to produce very realistic
texts by using a system of rules defined by a human. Complicated
grammars can hide large volumes of data in seemingly human bab-
ble. This babble could be posted to some Internet newsgroup, and it
will be hard to tell the difference between this and the randomflames
and cascading comments that float through the linguistic ether.
There are still other levels of abstraction that are possible. MUDs
(Multiple-User Dungeons) allow users to meet up in a text-based
world defined and built up by textual architects. It is possible to
meet people in the MUD rooms and hold conversations in the same
way that youmight ordinarily talk. SomeMUDs now sport computer
programs that pretend to be human in the spirit of the great Eliza
[Wei76]. These programs use complicated grammars to guide the
3
This might be modeled with queuing theory.
