Section outline

  • January 7th, Wednesday (10:30-12:30)

    Exercises

    • State whether the languages \( L_1 = \{ a^n a^m b^n c^m \; | \; n, m \geq 1 \} \) and \( L_2 = \{ a^n a^n b^n c^n \; | \; n \geq 1 \} \) are context-free (exercise from final exam of June 28th, 2021)
    • Let \( {\cal P} = \{ L \; | \; L \in {\rm RE} \), for every string \( w \in L \) we have \( \#_0(w) \lt \#_1(w) \} \)
      • Use Rice’s theorem to show that \( L_{{\cal P}} \) is not in REC
      • Prove that \( L_{{\cal P}} \) is not in RE
      (exercise from final exam of July 3rd, 2025)
    • Assess whether the following statements are true or false
      • For every languages \( L_1 \) in REG and \( L_2 \) in REC, we have that \( L_1 \cap L_2 \) is in REG
      • For every languages \( L_1 \) in REG and \( L_2 \) in REC, we have that \( L_1 \cap L_2 \) is in REC
      • There exist languages \( L_1, L_2 \) in CFL\( \smallsetminus \)REG such that the language \(L_1 \cap L_2\) is in REG
      • Let \({ \cal P }\) be the class of languages that can be recognised in polynomial time by a TM. For every languages \(L_1\) in CFL and \(L_2\) in \({\cal P}\), we have that \(L_1 \cdot L_2\) is in \({\cal P}\)
      (exercise from final exam of September 11th, 2025)