Section outline

  • October 20th, Friday (12:30-14: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
    • Show that the language \( \{ ww^R \; | \; w \in \{0,1\}^* \} \) is not regular, where \(R\) is the string reversal operator

    References

    • Hopcroft et al., chapter 4