[COURSE INFORMATION]

COMP 272--NOTES

This page gives access to any online lecture units that I have prepared.

I have added the corresponding section numbers for Kinber & Smith's material in the following DW Units.

Each entry is in square brackets.

Teaching order: I will teach most of the lecture units in the given order.

This term I am delaying Unit 4 until we have finished Unit 8.

  • Unit 1: TECHNICALITIES; MOTIVATION AND OVERVIEW.

    Notes on ISO Standard C++ and the string class; in PostScript and in four-page format.

  • Unit 2: SETS, RELATIONS AND FUNCTIONS.
    [Sets, relations and functions: 1.4]

  • Unit 3: REGULAR EXPRESSIONS.
    [Regular expressions: 2.4]

  • Unit 5: FINITE-STATE MACHINES.
    [Finite-state machines (FSMs): 2.1]

  • Unit 6: NONDETERMINISTIC FINITE-STATE MACHINES.
    [Deterministic finite-state machines (FSMs): 2.2]

  • Unit 7: THE FUNDAMENTAL THEOREM.
    [The fundamental theorem: 2.3 & 2.6]

    Unit 7elim: Figures for State Elimination

  • Unit 8: REGULAR LANGUAGE PROPERTIES.
    [Regular language properties: 2.4]

  • Unit 4: COUNTABILITY.
    [Countability: 5.1]

  • Unit 9: PROVING NONREGULARITY.
    [Nonregular languages: 2.5]

    Unit 9Alice: ALICE & BOB & THE REGULAR PUMPING LEMMA.

    Unit 9Bob: BOB & ALICE & THE REGULAR PUMPING LEMMA.

    Unit 9PL: NEGATIVE USE OF REGULAR PUMPING LEMMA.

  • Unit 10: CONTEXT-FREE GRAMMARS.
    [Context-free languages: 3.1]

    Unit 10 Supplement: An XML example.

  • Unit 11: PUSHDOWN MACHINES.

  • Unit 12: THE FUNDAMENTAL THEOREM.

  • Unit 13: CLOSURE PROPERTIES OF CFLS.

  • Unit 14: PROVING NON-CONTEXT-FREENESS.

  • Unit 15: TURING MACHINES.

  • Unit 16: TURING MACHINES AND LANGUAGES.

  • Unit 17: CLOSURE PROPERTIES.

  • Unit 18: UNIVERSAL TURING MACHINES.

  • Unit 19: DECIDABILITY.

  • Unit 20: AN UNDECIDABLE PROBLEM.

    • Last updated 15/02/2005 by Derick Wood