Section outline

  • December 13th, Friday (08:30-10:30)

    Exercises

    • Answer the following yes/no questions, providing a motivation (exercise from final exam of June 28th, 2019)
      • If \( L_1 \) is in REC and \( L_2 \) is in RE, is \( L_1 \cap L_2 \) always in REC?
      • If \( L_1 \) is in REC and \( L_2 \) is in RE, is \( L_1 \cap L_2 \) always outside of REC?
    • Let \(L_{ev}\) be the language of all strings in \(\{0,1\}^\ast\) with even length. Define \({\cal P} = \{ L \; | \; L \in {\rm RE}, \; L_{ev} \subsetneq L \} \) and define \( L_{\cal P} = \{ \mathsf{enc}(M) \; | \; L(M) \in {\cal P} \} \). Is \(L_{\cal P}\) a recursive language? (exercise from final exam of January 22nd, 2019)
    • Let \(L_1\) and \(L_2\) be recursive languages. Is \(L_1 L_2\) a recursive language? (exercise from final exam of January 22nd, 2019)
    • Let \(L = \{ enc(M_1, M_2) \; | \; L(M_1) \subseteq L(M_2) \} \) with \(M_1, M_2\) TMs. Is \(L\) a recursively enumerable language? (exercise from final exam of January 22nd, 2019)

    References

    • Hopcroft et al., chapter 9