Section outline

  • November 7th, Friday (10:30-12:30)

    Push-down automata

    • Intuitive idea
    • The stack auxiliary memory
    • Move typologies for PDA
    • Definition of push-down automaton (PDA)
    • Graphical representation of the transition function
    • Instantaneous description and computation step
    • Definition of computation for a PDA
    • Examples

    Exercises

    • Write a CFG for the language \( L = \{ w \; | \; w = a^i b^j c^{i+j} \; | \; i,j \geq 1 \} \)

    References

    • Hopcroft et al., chapter 6