Chapter 8: LR(k) Grammars ~ 273
only A --+ b can be the last production in the rightmost derivation of aPIl+lc.
(We do not have (lAc and Abb as substrings of ab
2n +] c). Similarly the last
productions for aAc and aAb
21l c are 5 --+ aAc and A --+ Abb respectively.
Hence G is an LR(O) grammar.
EXAMPLE 8.5
Show that S --+ aAb, A --+ cAc I c is not LR(k) for any natural number k.
Solution
It is easy to see that
L(G) = {ac
2n +
1
b 111 2' : O}
Consider aeccb E L(G). The last production is A --+ c. But we can apply this
handle only by knowing the entire string. Tnis can be applied to the middle c
but this is knO\vn only after looking at two symbols beyond the c which
replaces A. Continuing this argument, we can decide the handle of ac
21l
+
1
b by
only looking at n + 1 symbols beyond the c which replaces A. So it is not
LR(k) for any k.
EXAMPLE 8.6
Give an example of a language which can be generated by an LR(k) gram..'11ar
for some k and also by a grammar that is not LR(k) for any k.
Solution
Consider {ac
21l +
1
b In : : : : O}. This is generated by the grammar 5 --+ aAb.
A --+ cAc I c which is not LR(k) for any k.
This language can also be generated by the grammar S --+ aAb,
A --+ Acc I c. This is LR(O). (This grammar is similar to the grammar in
Example 8A.)
SELF-TEST
Choose the correct answer to Questions 1-5:
1. An LR(k) grammar has to be
(a) a type 0 grammar
(b) a type 1 grammar
(c) a type 2 grammar
(d) none of these.
~
An LR(k) gram..'11ar is
(a) ahvays unambiguous
(b) always ambiguous
(c) need not be unambiguous
(d) none of these.