Section outline

  • November 7th, Thursday (08:30-10:30)

    Context-free grammars

    • Rewrite relation, reflexive and transitive closure
    • Derivation, leftmost derivation and rightmost derivation
    • Language generated by a CFG
    • Sentential forms for a CFG
    • Derivation composition
    • Derivation factorisation

    Exercises

    • Write a CFG for the language \( L \) of all strings with balanced parentheses (assume \( \varepsilon \not \in L \))
    • Write a CFG for the language \( L = \{ w \; | \; w = a^i b^j c^k, \; i, j, k \geq 1 \} \)

    References

    • Hopcroft et al., chapter 5