Section outline

  • October 23rd, Thursday (14:30-16:30)

    Properties of regular languages

    • Closure properties of regular languages: union, concatenation, Kleene star, language complementation
    • Closure of regular languages under intersection
    • Regular language intersection and intersection automaton
    • Closure under set difference operator
    • Closure under string reversal operator
    • Structural induction (chapter 1)
    • Regular expression for the reverse of a regular language

    Exercises

    • Show that the language \( \{ ww^R \; | \; w \in \{0,1\}^* \} \) is not regular, where \(R\) is the string reversal operator
    • Common mistakes in the application of the pumping lemma

    References

    • Hopcroft et al., chapter 4
    • Hopcroft et al., chapter 1 (structural induction, slides #27-#32 from the lecture)