Section outline

  • October 23rd, Wednesday (10:30-12:30)

    Properties of regular languages

    • Intuitive idea underlying the pumping lemma for regular languages
    • Theorem: pumping lemma for regular languages

    Exercises

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

    References

    • Hopcroft et al., chapter 4