274 g, Theory of Computer Science
3. A handle is
(a) a string of variables and terminals
(b) a string of variables
(c) a string of terminals
(d) a production.
4. The automaton corresponding to an LR(k) grammar is
(a) a deterministic finite automaton
(b) a nondeterministic finite automaton
(c) a deterministic PDA
(d) a nondeterministic PDA.
5. J: dcfl is closed under
(a) union
(b) complementation
(c) intersection
(d) none of these.
EXERCISES
8.1 Show that the grammar 5 ~ aAb. A ~ aAb I a is an LR(l) or is it an
LR(O)?
8.2 Show that the grammar 5 ~ OA2, A ~ L4.1, A ~ 1 is not an LR(O).
8.3 Is 5 ~ AB, 5 ~ aA, A ~ aA, A ~ a, B ~ a an LR(k) for some k?
8.4 Show that {a
lll b
ll1 c" IIn, 11 2' : I} u {a
lll b"c
l1
IIn, 11 2' : 1} cannot be generated
by an LR(k) grammar for any k.
8.5 Are the following statements true? (a) If G is unambiguous, it is LR(k)
for some k. (b) If G is unambiguous. it is LR(k) for every k. Justify your
answer.
8.6 Is 5 ~ C ID, C ~ aC Ib, D ~ aD Ian LR(O)?
8.7 For a production A ~ f3 of a context-free grammar G and w in L*$k
($ is a symbol not in Vv U L), define RkC'rv) to be the set of all strings
of the form af3~v such that A ~ f3 is a handle for af3ww' for some w'
in L* $* and 5$ :b aA,nv' => af3'vw'. (In other words, a string af3w is
R
R
in Rk(w) if we get a penultimate step of a rightmost derivation of af3ww'
for some w'.) Show that Rk(w) is a regular set.
[Hint: Define G' = (V'v, v.v U L, p', 5'), where
Vv= {[A, w] IA E V N , WE p$k and Iwi = k}
5' = [5, $k]