Section outline

  • December 15th, Friday (12:30-14: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

    Exercises

    • Let \( \Sigma = \{a,b\} \). State whether the following languages are regular (first three questions are from final exam of June 28th, 2019)
      • \(L_1 = \{ bbxbbx^R \; | \; x \in \Sigma^\ast \}\)
      • \(L_2 = \{ bbx \; | \; x \in \Sigma^\ast \} \cdot \{ bbx^R | x \in \Sigma^\ast \} \)
      • \( L_3 = \{ bbx \; | \; x \in \Sigma^\ast \} \cdot L_1 \cdot \{ bbx^R \; | \; x \in \Sigma^\ast \}\)
      • \( L_4 = \{ x \; | \; x \in \Sigma^\ast \} \cdot \{ xx^R \; | \; x \in \Sigma^\ast \} \cdot \{ x^R \; | \; x \in \Sigma^\ast \}\)

    References

    • Hopcroft et al., chapter 9