Section outline

  • November 21st, Tuesday (12:30-14:30)

    Properties of context-free languages

    • Example of pumping lemma for CFL
    • Properties of CFL that can be derived from the pumping lemma
    • Closure of CFL under substitution
    • Applications of the substitution theorem: closure of CFL under union, concatenation, Kleene closure, positive closure, and homomorphism

    Research & application highlights:

    • Context-free grammars
    • Natural language processing

    References

    • Hopcroft et al., chapter 7