Section outline

  • November 8th, Friday (08:30-10:30)

    Context-free grammars

    • Definition of parse tree
    • Standard terminology for parse trees
    • Relation between derivations, leftmost/rightmost derivations, and parse trees
    • The relation between derivations and parse trees is not one-to-one
    • Ambiguous CFGs
    • Inherently ambiguous CFGs
    • Transforming a regular expression into an equivalent CFG
    • Transforming a FA into an equivalent CFG

    Exercises

    • Write a CFG for the language \( L = \{ w \; | \; w = a^i b^j c^k, \; i, j, k \geq 1, \; j \neq k \} \)

    References

    • Hopcroft et al., chapter 5