Section outline

  • November 8th, Wednesday (12:30-14:30)

    Context-free grammars

    • Ambiguous CFGs
    • Inherently ambiguous CFGs
    • Transforming a regular expression into an equivalent CFG
    • Transforming a FA into an equivalent CFG

    Push-down automata

    • Intuitive idea
    • The stack auxiliary memory
    • Move typologies for PDA

    Exercises

    • Show that the language \( L = \{ a^i b^j c^{i+j} \; | \; i,j \geq 1 \} \) is a CFL, by writing a CFG \(G\) such that \(L(G) = L\)

    References

    • Hopcroft et al., chapter 5
    • Hopcroft et al., chapter 6