Section outline

  • November 22nd, Friday (08:30-10:30)

    Properties of context-free languages

    • Applications of the substitution theorem: closure of CFL under union,
      concatenation, Kleene closure, positive closure, and homomorphism
    • Closure of CFL under string reversal
    • CFL and intersection
    • Intersection between CFL and regular languages
    • Other closure properties for CFL
    • Computational analysis of transformations for CFG e PDA
    • Emptyness for CFL
    • Membership for CFL: the CKY algorithm
    • Undecidable problems for CFL

    References

    • Hopcroft et al., chapter 7