Section outline

  • October 24th, Thursday (08:30-10: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
    • 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