Section outline

  • November 15th, Wednesday (12:30-14:30)

    Properties of context-free languages

    • Algorithm for nullable symbols
    • Elimination of epsilon-productions
    • Algorithm for unary pairs
    • Elimination of unary productions
    • CFG simplification
    • Chomsky normal form
    • Examples

    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