Quiz 13

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.

1. (1p) Which of the following statements, if any, are correct for the PDA P?

   1. (p, 01, A) ⊢^* (p, 01, A)
   2. (p, 01, A) ⊢^* (p, 01, B)
   3. (p, 01, A) ⊢^* (q, 01, B)
   4. (p, 01, A) ⊢^* (q, 1, B)
   5. (p, 01, A) ⊢^* (p, ε, B)
   6. (p, 01, A) ⊢^* (q, ε, ε)
   7. (q, 101, AB) ⊢^* (q, ε, ABAB)
   8. (q, 101, AB) ⊢^* (q, ε, BABA)

2. (1p) Which of the following strings, if any, are members of the language L(P)?

   1. 00
   2. 01
   3. 10
   4. 11

3. (1p) Which of the following statements, if any, are correct for the TM M?

   1. q₀0101 ⊢^* 01q₁01
   2. q₀0101 ⊢^* 01q₂01
   3. q₀0101 ⊢^* 11q₁01
   4. q₀0101 ⊢^* 11q₂01
   5. q₀0101 ⊢^* 1111q₀␣
   6. q₀0101 ⊢^* 1111q₁␣
   7. q₀0101 ⊢^* 1111q₂␣

4. (1p) Which of the following strings, if any, are members of the language L(M)?

   1. 00
   2. 01
   3. 10
   4. 11

5. (1p) For which of the following strings, if any, does the Turing machine M halt?

   1. 00
   2. 01
   3. 10
   4. 11