Section outline

  • October 31st, Tuesday (12:30-14:30)

    Properties of regular languages

    • Equivalence of regular languages
    • Minimization of DFAs

    Exercises

    • 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)
    • State whether the language \( L_1 = \{w \; | \; w \in \{a,b\}^*, \; \#_b(w)  \leq  \#_a(w)  ≤  2 \#_b(w) \} \) is a regular language
    • State whether the language \( L_2 = \{w \; | \; w \in \{a,b\}^*, \; \#_a(w)  \neq  \#_b(w), \;  \#_a(w)  \neq  2 \#_b(w) \} \) is a regular language
    • Let \(\Sigma = \{a,b\}\) and let \(L = \{w w' \; | \; |w| = |w'|, w \neq w'\}\). Prove that \(L\) is not a regular language.

    References

    • Hopcroft et al., chapter 4