Sketch of Solutions to Exercises

[source]

(a) Choose w = a^mb^m+1c^m+2

(b) Choose w = a^mb^mb^ma^ma^mb^m = a^mb^2ma^2mb^m

(c) Choose w = a^mb^ma^mb^m

(d) Choose w = a^2m+1b^2ma^2m+1b^2m

(e) Choose w = a^mb^m#a^mb^m

(f) Choose w = a^m!

w_o = a^m!-j for some 0 < j < m

For m > 2 we have

(m - 1)! < m((m - 1)! - 1) = m! - m < m! - j < m! - 1 < m!

Thus

(m - 1)! < |w_o| < m! for m > 2 and in such a case w_o is not in L.

If m = 1 then w = a and w = uvxyz vy = 1 w³ = a₃ not in L

If m = 2 then (w = aa and w = uvxyz vy = a w₃ = a³ not in L) or (vy = aa w₂ = a⁴ not in L)

L not cfl.

3.4.3 Choose (w₁, w₂) = (a^mb^mc^m, d^m)

Consider any decomposition

w₁ = u₁v₁x₁y₁z₁

w₂ = u₂v₂x₂y₂z₂

If v₂y₂ = then choose k = 0. In such a case (u₁v₁⁰x₁y₁⁰z₁, u₂v₂⁰x₂y₂⁰z₂) = (a^m-j₁b^m-j₂c^m-j₃, d^m) with j₁ > 0 or j₂ > 0 or j₃ > 0.

If v₂y₂ /= then choose k = 2. In such a case (u₁v₁²x₁y₁²z₁, u₂v₂²x₂y₂²z₂) = (a^m+j₁b^m+j₂c^m+j₃, d^m+j₄) with j₄ > 0 and either j₁ = 0 or j₂ = 0 or j₃ = 0.