Section outline

  • November 15h, Friday (08:30-10:30)

    Properties of context-free languages

    • Elimination of useless symbols
    • Algorithm for detecting generating symbols
    • Algorithm for detecting reachable symbols
    • Algorithm for detecting nullable symbols
    • Elimination of epsilon-productions

    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 7