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.
DFAs, regular languages, regular expressions, regular grammars, NFAs,
closure properties of RLs, converting an NFA into a DFA, the pumping lemma
Context-free grammars, pushdown automata, converting between CFGs and PDAs,
closure properties of CFLs, the pumping lemma for CFLs, non context-free
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.
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.
Introduction to the Theory of Computation
1st, 2nd or 3rd Edition
PWS Publishing Co.
C and C++ Books
Introduction to C. Deitel and Deitel
C++ for Programmers (3rd Edition)
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
Please don't print them yourself the notes are handed out in 4-up form
It is essential that you read study Sipser and do most of the exercises up
to the end of Chapter 4 in order to get to grips with the course.
Regular Expressions by Reg Dodds
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
Manual for flex version 2.6.0
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
Debugging with GDB 9th Ed
If you find any errors please report them by E-mail
Some useful ancient PostScript and newer PDFs for tutorials and may be found below
1tutorial.pdf (A4 format PDF)
2tutotrial.pdf (A4 format PDF)
3tutorial.pdf (A4 format PDF)
4tutorial.pdf (A4 format PDF)
2016 CSC311 Theory of Computation examination memorandum
Link to the 2016 examination memo.
2015 November CSC311 Theory of Computation examination paper and solution
Link to the November 2015 examination paper.
Link to a solution of the November 2015 ToC examination paper.
Please don't get cross when you find errors. Simply let me know.
2016 November CSC311 Theory of Computation Examination and Supplementary
Time: 14h30 Friday 20th January 2017
Venue: Proteaville Recreation Hall.
Located at the corner of:
Abdurahman Street and Peter Barlow Drive,
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.
Here is an ancient C tutorial that is not part of the 2016 CSC 311 TOC course but
may be useful for 2016 CSC 311 OS.
Link to C notes for Java programmers.
These notes for C provide some insights for Java programmers.
The latest version of all the material here is always available on zaber
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