Section outline

  • October 24th, Tuesday (12:30-14:30)

    Properties of regular languages

    • Closure properties of regular languages: union, concatenation, Kleene star, language complementation
    • Regular language intersection and intersection automaton
    • Closure under set difference operator
    • Closure under string reversal operator

    Exercises

    • Use structural induction to prove that if a regular expression \(R\) does not use the Kleen star operator \(\ast\), then \(L(R)\) is a finite language
    • Use structural induction to define a construction that, given a regular expression \(R\), provides a regular expression \(P(R)\) generating the language of all prefixes of strings in \(L(R)\)

    References

    • Hopcroft et al., chapter 4