Section outline

  • December 22th, Friday (12:30-14:30)

    Undecidability

    • Definition of the ambiguity problem for CFL and the associated language \(L_{\mathit{AMB}}\)
    • Reduction from PCP to \(L_{\mathit{AMB}}\)

    Exercises

    • 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