Section outline

  • November 17th, Friday (12:30-14:30)

    Properties of context-free languages

    • Lemma on parse trees in CNF
    • Proof of pumping lemma for CFL

    Exercises

    • Let \( L = \{ a^nb^n \; | \; n \geq 1 \} \) and let \( L' = \{ a,b \}^+ \). State whether the the following three languages are regular: \( L \cdot L' \), \( L' \cdot L \), \( L' \cdot L \cdot L' \)

    References

    • Hopcroft et al., chapter 7