Section outline

  • November 21st, Thursday (08:30-10:30)

    Properties of context-free languages

    • Definition of substitution
    • Closure of CFL under substitution

    Exercises

    • Show that the language \( L = \{ w \; | \; w \in \{a,b\}^\ast, \#_a(w) \not = \#_b(w) \} \) is a CFL
    • 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