Section outline

  • November 28th, Tuesday (12:30-14:30)

    Turing Machine

    • Language accepted by a TM
    • Language accepted by a TM that always halts
    • Recursive languages (REC) and recursively enumerable languages (RE)
    • Decision problems and associated languages (see chapter 1, section 1.5.4)
    • Decidable problems and recursive languages
    • Programming techniques for TM
    • State seen as a finite memory with random access
    • Multiple tracks on the tape

    Exercises

    Prove the truth or falsehood of the following statements (exercise from final exam of February 13th, 2019)
    • 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
    • Given a CFL \(L_1\), each subset of \(L_1\) is still a CFL
    • Given two languages \(L_1\) and \(L_2\) not in REG, the language \(L_1 \cup L_2\) cannot be in REG

    References

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