Sketch of Solutions to Exercises

m = 3

• x = , y = 011

• x = 01, y = 0

(a) Choose w = a^m+1b^m and k = 0

(b) Choose w = a^mb^m+1 and k = 2

(c) Choose w = a^mba^m and k = 0

(d) Choose w = 0^m10010^m and k = 0

(e) Choose w = a^m2

Then xy^kz = a^{n2 +(k-1)j}

For k = 0,

xy⁰z = aⁿ² - j

Since 0 < j < n

(n - 1)² < n(n - 1) = n² - n < n² - j < n²

(f) Choose w = a^rb^z for some r > m and t which will be determined later. Then

xy^kz = a^r+(k-1)jb^t

A contradiction arises if and only if r + (k - 1)j = t or k = (t - r)/j + 1.

The choice

t = m! + m, r = m

implies a positive integer number for k.

(g) Choose w = a^rba^tb for some r > m and t will be determined below. Then

xy^kz = a^r+(k-1)jba^tb

A contradiction will be implied if an only if r + (k - 1)j = t or k = (t - r)/j + 1. Hence, take

t = m! + m, r = m

(If m = 1 take 2 instead of m to ensure a string of even length.)

2.4.3 Let m be the number of states of a finite state transducer M that computes R. If |w| > m max{1, |v|} then M on input v repeats a state, where between the repetition M reads nothing and writes some y, i.e., y can be pumped.

2.4.4 Assume that the relation is computable by a finite state transducer. Let M be the constant that Exr 2.4.3 implies for the relation. The pair (a^m2 b^m, c^m4 ) is in the relation. However, the implied pairs (a^m2 b^m2 , c^m4 + (k - 1)j) are not there for k > 1, that is, the result in Exr 2.4.4 does not apply for the relation.