Section outline

  • November 28th, Friday (10:30-12:30)

    Turing Machine

    • Decidable problems and recursive languages
    • Programming techniques for TM
    • State seen as a finite memory with random access
    • Multiple tracks on the tape
    • Use of subroutines

    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