Section outline

  • November 5th, Wednesday (10:30-12: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_1 \) of all strings with balanced parentheses (assume \( \varepsilon \not \in L \))
    • Write a CFG for the language \( L_2 = \{ w \; | \; w = a^i b^j c^k, \; i, j, k \geq 1 \} \)
    • Write a CFG for the language \( L_3 = \{ w \; | \; w = ba^nba^nb, \; n \geq 1 \} \)
    • Write a CFG for the language \( L_4 = \{ w \; | \; w = a^i b^j c^k, \; i, j, k \geq 1, \; j \neq k \} \)

    References

    • Hopcroft et al., chapter 5