Section outline

  • November 3rd, Friday (12:30-14:30)

    Context-free grammars

    • Introduction to context-free grammars (CFGs)
    • Definition of CFG
    • Rewrite relation, reflexive and transitive closure
    • Derivation, leftmost derivation and rightmost derivation
    • Language generated by a CFG

    Exercises

    • CFG for language \( L \) of all strings with balanced parentheses (assume \( \varepsilon \not \in L \))

    References

    • Hopcroft et al., chapter 5