Section outline

  • October 30th, Wednesday (10:30-12:30)

    Properties of regular languages

    • Closure of regular languages under homomorphism application
    • Time complexity for standard conversions

    Exercise

    • Let \(M\) be a DFA over alphabet \(\{0,1\}\) with initial state \(q_0\), final states \(q_2, q_3\) and transition function \(\delta(q_0,0) = q_1\), \(\delta(q_0,1) = q_0\), \(\delta(q_1,0) = q_2\), \(\delta(q_1,1) = q_3\), \(\delta(q_2,0) = q_0\), \(\delta(q_2,1) = q_0\), \(\delta(q_3,0) = q_3\), \(\delta(q_3,1) = q_0\). Convert \(M\) into a regular expression using the technique of state elimination (exercise from final exam of January 22nd, 2019)
    • 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

    References

    • Hopcroft et al., chapter 4