Cryptography Reference
In-Depth Information
the order. Bits of information can only be recalled from the stack in
the reverse order in which they were put onto the stack. There is no
way to dig deeper.
It is possible to offer you solid proof that push-down automata
are the ideal computational model for describing the behavior of
context-free grammars, but that solution is a bit dry. A better ap-
You can find a good
proof in [AHU83].
proach is to illustrate it with a grammar:
start
→
Thelma and Louise
what when
Harry and Louise
what when
what
→
went shooting
with where
bought insurance
with where
with
→
with Bob and Ray
with Laverne and Shirley
→
when
on Monday.
on Tuesday.
on Wednesday.
on
Thursday.
where
→
in Kansas
in Canada
A typical sentence produced by this grammar might be “Thelma
and Louise went shooting with Bob and Ray in Kansas on Monday.”
This was produced by making the first choice of production from
each variable and thus hiding the six bits 000000. But when the first
choice was made and Thelma and Louise became the subjects of the
sentence, the question about the date needed to be stored away until
it was needed later. You can either think of the sentence as develop-
ing the leftmost variable first or you can think of it as choosing the
topmost variable from the stack. Here's a table showing how a sen-
tence was produced. It illustrates both ways of thinking about it.
Stack
Pending Sentence
Pending with Variables
start
noun
what
Thelma and Louise
Thelma and Louise
what
when
when
with
Thelma and Louise went
Thelma and Louise went
where
shooting
shooting
with where
when
where
Thelma and Louise went
Thelma and Louise went
when
shooting with Bob and Ray
shooting with Bob and Ray
where when
when
Thelma and Louise went
Thelma and Louise went
shooting with Bob and Ray
shooting with Bob and Ray
in Kansas
in Kansas
when
empty
Thelma and Louise went
Thelma and Louise went
shooting with Bob and Ray
shooting with Bob and Ray
in Kansas on Monday.
in Kansas on Monday.
