Section outline

  • November 27th, Thursday (14:30-16:30)

    Turing Machine

    • TM with output
    • 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)

    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