Section outline

  • December 5th, Friday (10:30-12:30)

    Undecidability

    • The TM / string infinite table
    • Diagonalization language \( L_d \)
    • \( L_d \) is not in RE
    • Properties of recursive languages
    • Properties of RE languages

    Exercises

    • Assume \( \Sigma = \{ a, b, c \} \). State whether the following languages are regular or not (exercise from final exam of September 3rd, 2021)
      • \( L_1 = \{ w \; | \; w = XuYvZ, \; X,Y,Z \in \Sigma, \; u,v \in \Sigma^\ast, \; X = Z, \; |u| = |v| \} \)
      • \( L_2 = \{ w \; | \; w = XuYvZ, \; X,Y,Z \in \Sigma, \; u,v \in \Sigma^\ast, \; X = Y = Z \} \)
      • \( L_3 = \{ w \; | \; w = XuYvZ, \; X,Y,Z \in \Sigma, \; u,v \in \Sigma^\ast, \; X = Y = Z, \; |u| = |v| \} \)

    References

    • Hopcroft et al., chapter 9