Section outline

  • November 20th, Thursday (14:30-16:30)

    Properties of context-free languages

    • Definition of substitution
    • Closure of CFL under substitution
    • Applications of the substitution theorem: closure of CFL under union,
      concatenation, Kleene closure, positive closure, and homomorphism

    Exercises

    • Show that the language \( L = \{ w \; | \; w \in \{a,b\}^\ast, \#_a(w) \not = \#_b(w) \} \) is a CFL

    References

    • Hopcroft et al., chapter 7