Section outline

  • October 22nd, Wednesday (10:30-12:30)

    Properties of regular languages

    • The pigeonhole principle (chapter 2)
    • Intuitive idea underlying the pumping lemma for regular languages
    • Theorem: pumping lemma for regular languages
    • Notion of implication (chapter 1)

    Exercises

    • Show that the language \( L_{eq} = \{ w \; | \; w \in \{0,1\}^\ast, \; \#_0(w) = \#_1(w) \} \) is not regular

    References

    • Hopcroft et al., chapter 4
    • Hopcroft et al., chapter 2 (pigeonhole principle, box in section 2.3.6)
    • Hopcroft et al., chapter 1 (implication, slides #11, #12 from the lecture)