Section outline

  • November 14th, Tuesday (12:30-14:30)

    Push-down automata

    • 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

    Properties of context-free languages

    • Elimination of useless symbols
    • Algorithm for generating symbols
    • Algorithm for reachable symbols

    Exercises

    • Specify a PDA recognising the language \( L = \{ a^i b^j c^{i+j} \; | \; i,j \geq 1 \} \). Informally explain the meaning of each state of the PDA

    References

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