Section outline

  • November 22nd, Wednesday (12:30-14:30)

    Properties of context-free languages

    • 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