Section outline

  • November 28th, Thursday (08:30-10: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
    • Programming techniques for TM: examples
    • Use of subroutines
    • Programming techniques for TM: examples

    Exercises

    Prove the truth or falsehood of the following statements (exercise 3 from final exam of February 13th, 2019)
    • Given two languages \(L_1\) and \(L_2\) not in REG, the language \(L_1 \cup L_2\) cannot be in REG
    • Given a CFL \(L_1\), each subset of \(L_1\) is still a CFL
    • Given a CFL \(L_1\) and given a language \(L_2\) in REG, the language \(L_1 \cap L_2\) can be in REG
    • Given a CFL \(L_1\) and given a language \(L_2\) in REG, the language \(L_1 \cap L_2\) may not be in REG

    References

    • Hopcroft et al., chapter 8
    • Hopcroft et al., chapter 1