Section outline

  • December 20th, Wednesday (12:30-14:30)

    Undecidability

    • Properties \( \cal P\) of RE languages and associated languages \( L_\cal P\)
    • Rice's theorem
    • Discussion
    • Definition of Post's correspondence probem (PCP)
    • Example
    • PCP is not recursive (no proof)

    Exercises

    • Let \(\Sigma = \{a,b\}\). State whether the following languages are regular (final exam of September 19th, 2022)
      • \( L_1 = \{ w \; | \; w = a^pba^q, \; p,q \geq 0, \; 1 \leq p + q \} \)
      • \( L_2 = \{ w \; | \; w = a^pba^q, \; p,q \geq 0, \; 1 \leq p - q \} \)
      • \( L_3 = \{ w \; | \; w = a^pba^q, \; p,q \geq 0, \; p = q^3 \mbox{ or } q = p^3 \} \)

    References

    • Hopcroft et al., chapter 9