CSC 311 Theory of Computation

Second semester 2016


.

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.

    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.
    This did not materialize in 2016.

  • 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