Section outline

  • November 29th, Wednesday (12:30-14:30)

    Turing Machine

    • Programming techniques for TM: examples
    • Use of subroutines
    • Extension of TM
    • Multi-tape TM

    Exercises

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

    References

    • Hopcroft et al., chapter 8