Section outline

  • December 5th, Thursday (08:30-10:30)

    Undecidability

    • \( L_d \) is not in RE
    • Properties of recursive languages
    • Properties of RE languages
    • Universal Language \( L_u \)

    Exercises

    • Let \( \Sigma = \{ a, b, c \} \); consider the language \(L = \{ w \; | \; w \in \Sigma^\ast, \; \#_a(w) = \#_b(w) = \#_c(w) \}\). Show that \(L\) is not a CFL
    • 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