CSC 311 Theory of Computation

Second semester 2017


Theory of Computation

This course is an introduction to the Theory of Computation. The theory of Finite State Automata in their guises as regular languages, grammars and expressions and their applications in lexical analysers and regex machines. Context-free grammars and their recognition and their applications in parsers. Turing Machines. What they can do and what their limitations are. The halting problem.


  • At the successful completion of this course the student has successfully implemented some DFAs, implemented NFA → DFA, used flex, applied bison to grammars describing some small languages, programmed a generator for first and follow sets for a given grammar; solved some theoretical exercises; understood the halting problem; etc.

  • The student will cultivate a positive outlook and will develop the attitude that theory is useful because it can be applied to everyday problems in computing. The student will understand the power of finite state machines, context-free languages and Turing machines. The student will be conversant with tools that apply regular expressions and context-free languages to problems. The student will have emulated several machines.

  • Framework of the course.

    This is a mindmap for CSC311 Theory of Computation.
  • DFAs, regular languages, regular expressions, regular grammars, NFAs, closure properties of RLs, converting an NFA into a DFA, the pumping lemma for RLs.

  • Context-free grammars, pushdown automata, converting between CFGs and PDAs, closure properties of CFLs, the pumping lemma for CFLs, non context-free languages.

  • Turing machines

  • Decidability, the halting problem, a TM unrecognizable language

  • Apply flex and apply bison to solve practical problems.

  • Practicals and projects

  • Practical implementation of course work will be handed in weekly. A tutorial will also be conducted weekly to exercise the theory.

  • Class material

  • All the transparencies for the course are available below in A4- or four-per-A4-format. The 4-per-A4 slide copies will be issued in class. Please don't print them yourself. The Latex for my own notes is available on request. You may download the complete manual for make, flex and bison. Since we are using a Sun system you will be using lex and yacc in the lab.
  • Since all the documentation is available in PDF you might want to adapt your net reader for reading PDF, otherwise you can download it and then read it with your favourite viewer.

    Prescribed Book

  • Introduction to the Theory of Computation
    1st, 2nd or 3rd Edition
    Michael Sipser
    PWS Publishing Co.

  • C and C++ Books

  • The C Programming Language
    by Brian Kernighan and Dennis M. Ritchie
    Prentice Hall. ISBN 0-13-110362-8

  • C How to Program. Deitel and Deitel
    Prentice Hall. ISBN 0-13-226119-7

  • C++ for Programmers (3rd Edition)
    Leen Ammeraal
    (2000) Wiley.

  • Other course material

  • The class overheads in big printable format are available as
    toc.pdf (A4 format)
    The slides are based loosely on Michael Sipser's book Introduction to the Theory of Computation and on Ken Louden's book Compiler Construction.
    Please don't print them yourself the notes are handed out in 4-up form in class.

  • It is essential that you read and study Sipser and do most of the exercises up to the end of Chapter 4 in order to get to grips with the course.

  • C for Java programmers slides cfromJava.pdf
    These slides are a quick introduction to C if you know Java.
  • The Linux Command Line TLCL.pdf
    An up-to-date guideline to the Linux command line by William Shotts.
  • Regular Expressions by Reg Dodds reNotes.pdf
    These notes are still in a transient state but are a useful guide to using regular expressions in flex, python and Java and of course in ToC. Read these RE notes carefully. They are packed with useful hints, guidelines and examples.

  • The class overheads in big presentation format are available as toc-present.pdf (A4 format)
  • For errata, etc. here is a link to Sipser: Introduction to the Theory of Computation

  • Introduction to Latex
    lshort.pdf Some PDF versions are hyperlinked.

  • Manual for make make.pdf

  • Manual for flex version 2.6.0 flex.pdf
  • The flex regular expression patterns on Pages 9–13 should be studied well.

  • Manual for bison version 2.2 bison.pdf and version 3.0.4 bison-3-0-4.pdf

  • Debugging with GDB 9th Ed gdb.pdf

  • If you find any errors please report them by E-mail

  • Some useful ancient PDFs for tutorials and may be found below
  • Tutorial 1
    1tutorial.pdf (A4 format PDF)
  • Tutorial 2
  • 2tutotrial.pdf (A4 format PDF)
  • Tutorial 3
  • 3tutorial.pdf (A4 format PDF)
  • Tutorial 4
  • 4tutorial.pdf (A4 format PDF)

    CSC311 Theory of Computation 2016 September 30 class test

  • Link to the 2016 DFA class test. There is also a question about the CYK algorithm.
  • 2016 CSC311 Theory of Computation examination memorandum

  • Link to the 2016 examination memo.
  • 2017 November possibly December CSC311 Theory of Computation Examination and Supplementary

  • Time: 14h00 27 November 2017
    Venue: B3 and B4
  • Turing machine emulator

  • There is a Turing machine emulator in the tarball Link to a Turing machine emulator and some data that it can decide. This is not a decider, but it works for all the correct data that has been supplied. Just download "tm.tgz". Untar "tm.tgz". Change directory into "tm", and run by applying "make". Fiddle with the data to try to understand the thing, e.g. run it on your own machine with its own data.
  • C notes

  • Here are my C tutorial slides that are part of the 2017 CSC 311 TOC course and may be useful for 2017 CSC 311 OS.
    Link to C notes for Java programmers.
    These notes are an introduction to C based on Java.
  • ToC Overview in PDF

  • Here is a version of this webpage in PDF. br> ToC overview in PDF.
    Another supposedly up-to-date version of this webpage.
  • The latest version of all the material here is always available on zaber in ~/../../notes/toc/.


    E-mail me at:
    My direct email is at 'uwc' and not at 'cs.sun' but mailing to the first address still gets to me.
    I have had that email address since the early 80s.
    24 November 2016