Section outline

  • October 31st, Friday (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_1 = \{ a^n b^n \; | \; n \geq 1 \} \)
    • Write a CFG for the language \( L_2 = \{ a^n b^m | n \geq m \geq 1 \} \)
    • Write a CFG for the language \( L_3 = \{ a^n b^{2n} \; | \; n \geq 1 \} \)
    • Write a CFG for the language \( L_4 = \{ a^n b^m \; | \; n, m \geq 1 \} \)

    References

    • Hopcroft et al., chapter 5