Section outline

  • November 7th, Tuesday (12:30-14:30)

    Context-free grammars

    • Sentential forms for a CFG
    • Derivation composition and derivation factorisation
    • 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

    Exercises

    • Write a CFG for the language \( L = \{ w \; | \; w = a^i b^j c^k, \; i, j, k \geq 1 \} \)
    • 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