Section outline

  • October 31st, Thursday (08:30-10:30)

    Properties of regular languages

    • Emptiness test for regular languages
    • Membership test for regular languages
    • Definition of equivalence for states of DFA
    • Equivalence test on states for DFA
    • Equivalence of regular languages

    Exercises

    • 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