In the following exercises P refers to the pushdown automaton ({p ,q},{0, 1},{A, B},δ,p,A,{q}), where δ is defined in the following way:

  δ(p,ε,A) = {(p,B)}
  δ(p,ε,B) = ∅
  δ(p,0,A) = ∅
  δ(p,0,B) = {(p,A), (q,B)}
  δ(p,1,A) = ∅
  δ(p,1,B) = {(p,B)}
  δ(q,ε,A) = ∅
  δ(q,ε,B) = {(q,ε)}
  δ(q,0,A) = {(q,ε)}
  δ(q,0,B) = ∅
  δ(q,1,A) = {(q,ABA)}
  δ(q,1,B) = ∅

Furthermore M refers to the Turing machine ({q₀, q₁, q₂, q₃, q₄},{0, 1},{0, 1, ␣},γ,q₀,␣,{q₄}), where γ is defined in the following way:

  γ(q₀,0) = (q₁,1,R)
  γ(q₀,1) = (q₂,0,R)
  γ(q₀,␣) = (q₁,␣,L)
  γ(q₁,0) = (q₃,0,L)
  γ(q₁,1) = (q₂,1,R)
  γ(q₁,␣) = (q₀,␣,R)
  γ(q₂,0) = (q₁,1,R)
  γ(q₂,1) = (q₄,1,L)
  γ(q₂,␣) = (q₀,␣,R)

Note that γ(q₃,X) and γ(q₄,X) are undefined for all tape symbols X.