Section outline

  • November 14th, Thursday (08:30-10:30)

    Push-down automata

    • 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
    • Transformation of a CFG into a PDA by simulation of leftmost derivations: main construction, no proof of correctness
    • Transformation of a PDA into a CFG: statement only, no proof

    References

    • Hopcroft et al., chapter 6