# 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.
### Outcomes

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
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

Introduction to C. Deitel and Deitel

Prentice Hall.

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 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
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 PostScript and newer 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)

### 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,

Belleville South.

### 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 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
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*