Section 9.5 Formal Languages
793
of moves exists that causes it to halt in a final state. Any set recognized by an lba
can be shown to be a context-sensitive language, and conversely.
Figure 9.27 shows the relationship between the hierarchy of languages and the
hierarchy of computational devices.
C o n t e x t
- f r e e
rec o g n i z e d
b y p d a
C o n t e
x t - s e n s i ti v e
re c o g n i z e d
b y l b a
T y
p e 0
re co gnized by T u r in g m a c h i
n e
Regular
recognized by
finite-state machine
figure 9.27
Context-free Grammars
Context-free grammars are important for three reasons. Context-free grammars
seem to be the easiest to work with, since they allow replacing only one symbol at
a time. Furthermore, many programming languages are defined such that sections
of syntax, if not the whole language, can be described by context-free grammars.
Finally, a derivation in a context-free grammar has a nice graphical representation
called a parse tree.
example 59
The grammar of Example 54 is context-free. The word d2q can be derived
as follows: identifier 1 identifier letter 1 identifier digit letter 1 letter digit
letter 1 d digit letter 1 d2 letter 1 d2q. We can represent this derivation as a
tree with the start symbol for the root. When a production is applied to a node, that
node is replaced at the next lower level of the tree by the symbols in the right-hand
side of the production used. A tree for the derivation appears in Figure 9.28.
figure 9.28