Section outline

  • November 6th, Wednesday (10:30-12:30)

    Properties of regular languages

    • Minimization of DFAs

    Context-free grammars

    • Introduction to context-free grammars (CFGs)
    • Definition of CFG
    • Examples

    Exercises

    • Write a CFG for the language \( L = \{ a^n b^n \; | \; n \geq 1 \} \)
    • Write a CFG for the language \( L = \{ a^n b^m | n \geq m \geq 1 \} \)

    References

    • Hopcroft et al., chapter 5