Section outline

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

    Push-down automata

    • Definition of push-down automaton (PDA)
    • Graphical representation of the transition function
    • Instantaneous description and computation step
    • Definition of computation for a PDA
    • Examples
    • Computational properties of PDAs
    • Acceptance under final state and acceptance under empty stack
    • Transformation of an empty stack PDA into a final state PDA and proof of correctness
    • Transformation of a final state PDA into an empty stack PDA and proof of correctness

    References

    • Hopcroft et al., chapter 6