Section outline

  • November 15th, Friday (10:30-12:30)

    Properties of context-free languages

    • Algorithm for detecting unary pairs
    • Elimination of unary productions
    • CFG simplification
    • Definition of Chomsky normal form
    • Transformation of a CFG in Chomsky normal form
    • Examples

    Exercises

    • Use structural induction to define a construction that, given a regular expression \(R\), provides a regular expression \(P(R)\) generating the language of all prefixes of strings in \(L(R)\)

    References

    • Hopcroft et al., chapter 7