Section outline

  • December 6th, Friday (08:30-10:30)

    Undecidability

    • Universal TM \( U \)
    • \( L_u \) is in RE
    • \( L_u \) is not in REC (\(L_d \leq_m \overline{L_u}\))
    • Halting problem for a TM on a given input

    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)
    • 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