Section outline

  • November 26th, Wednesday (10:30-12:30)

    Properties of context-free languages

    • Computational analysis of transformations for CFG e PDA
    • Emptyness for CFL
    • Membership for CFL: the CKY algorithm
    • Undecidable problems for CFL

    Turing Machine

    • General ideas about Turing Machine (TM)
    • Mathematical definition of TM
    • Instantaneous description of a TM
    • Computation of a TM
    • Example of computation of a TM
    • Graphical representation of the transition function of a TM

    References

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