Section outline

  • December 19th, Tuesday (12:30-14:30)

    Undecidability

    • \( L_{ne} \) is not in REC (\(L_u \leq_m L_{ne}\))
    • \( L_{e} \) is not in RE

    Exercises

    • Let \( G \) be the CFG with productions \(S \rightarrow AC\), \(A \rightarrow BA \; | \; a\), \(B \rightarrow b\), \(C \rightarrow BC \; | \; c\). Apply the CYK agorithm to the string \( w = bbabbbc \) (exercise from final exam of June 28th, 2019)
    • Answer to 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?
      • 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 \( r = (ab+aab)^\ast \). Convert \(r\) into an equivalent \(\varepsilon\)-NFA (exercise from final exam of June 28th, 2019)

    Refereces

    • Hopcroft et al., cap. 9