Section outline

  • December 11th, Wednesday (10:30-12:30)

    Undecidability

    • Notion of reduction between two decision problems
    • Properties of reduction
    • Definition of languages \( L_{e} \) and \( L_{ne} \)
    • \( L_{ne} \) is in RE
    • \( L_{ne} \) is not in REC (\(L_u \leq_m L_{ne}\))
    • \( L_{e} \) is not in RE

    Exercises

    • Let \( r = (ab+aab)^\ast \). Convert \(r\) into an equivalent \(\varepsilon\)-NFA (exercise from final exam of June 28th, 2019)
    • Answer the following yes/no questions, providing a motivation (exercise from final exam of June 28th, 2019)
      • Is REC closed under intersection?
      • Is RE closed under intersection?

    Refereces

    • Hopcroft et al., cap. 9