408 Q Solutions (or Hints) to Chapter-end Exercises
derivations of 01
2k +
1
2 and 01
2k +
3
2 given by:
S ~ 01 kAl k 2 ~ 01
2k +
1
2 = af3w
R
R
where a = 01\ f3 = a, W = 1
k 2.
S ~ 01 k + 1 A1 k + 1 2 ~ OI 2k + 3 2 :::} a'{3'w'
R
R
(A8.I)
(A8.2)
where a' = 01k+l, f3' = a, w' = l'k+12. As the strings formed by the
first 2k + 1 symbols (note laf31 + k = 2k + 1) of af3w and a'{3'w' are
the same. a = at, i.e. Ol
k
=01
k +
1
, which is a contradiction. Thus the
given grammar is not LR(k) for any k.
8.3 The given grammar is ambiguous and hence is not LR(k) for any k.
For example, there are two derivation trees for abo
8.4 As a"b"e" appears in both the sets, it admits two different derivation
trees. So the set cannot be generated by an unambiguous grammar.
Chapter 9
9.2 The set of quintuples representing the TM consists of q 1 bILq2,
qIOORql, q:bbRq3' q:OOLq2, q211Lq2, q30bR% q3 1bRqs· q4bORqs,
q400Rq4, q4IIRq4. Q S bOLq2'
9.3 The computation for the first symbol 1 is qjllbll f-c- bq2bIl.
Afterwards it halts.
9.4 The computation sequence for the substring 12 of 1213 is
q j I213 f-c- bq2213 f-c- bbq3 13 .
As 8(q3' 1) is not defined, the TM halts. For 2133 and 312 the TM
does not start.
9.6 Modify the construction given in Example 9.7.
9.8 We have the following steps for processing the even-length
palindromes:
(a) The Turing machine M scans the first symbol of the input tape
(0 or 1), erases it and changes state (qj or q2)'
(b) M scans the remaining part without changing the tape symbol
until it encounters b.
(c) The RJW head moves to the left. If the rightmost symbol tallies
with the leftmost symbol (which can be erased but remembered),
the rightmost symbol is erased. Otherwise M halts.
(d) The R/W head moves to the left until b is encountered.
Steps (a), (b). (c), (d) are repeated after changing the states suitably.
The transition table is defined by Table A9.1.