Section outline

  • November 29th, Friday (08:30-10:30)

    Turing Machine

    • Extension of TM
    • Multi-tape TM
    • Nondeterministic TM
    • TM with restrictions
    • TM with semi-infinite tape

    Exercises

    • State whether the following languages are in CFL (exercise 2 from final exam of February 13th, 2019):
      • \( L_1 = \{ a^n b a^n b a^m\; | \; n,m \geq 1, \; m \geq n \} \)
      • \( L_2 = \{ a^n b a^p b a^m\; | \; n,p,m \geq 1, \; m \geq n \} \)

    References

    • Hopcroft et al., chapter 8