• Main page

Introduction

Mathematical background

I assume that the reader knows what a natural number is.

There is a genuine hard-core proof by induction (Kleene's theorem) but it is not examinable.

There are some ideas from Logic that readers will find helpful: it will help them if they know what conjunctive and disjunctive normal form are tho' it's not necessary; Universal Generalisation and ∀-introduction would help too, but chiefly for Kleene's theorem which is not examinable. Congruence relations are mentioned. Disjoint unions appear too.

We will be using the asterisk symbol: *, in more than one way. We will do the same with the two vertical bars ||. When a symbol is used in two related ways, we say it is overloaded.

Useful URLs and other materials

There are many of course. Here are three that have been recommended to me.

• I've tutored courses using the material on
  
  http://www.cl.cam.ac.uk/Teaching/2002/RLFA/reglfa.ps.gz
  
  This is the course material used at Cambridge for their 12-lecture course. It looks daunting and mathematical, but it's actually very well designed and thought through, so as long as you read it carefully you will be OK. However, it does make use of ε-transitions (which i hate! and do not make much use of here)


• My colleague Richard Crouch has some useful teaching material on his home page. Look under http://www.parc.com/crouch. Under "Teaching Material" you will find pdf files for "Formal Language Theory".


• JFLAP is a complete package for doing almost anything relating to fsa, cfg, tm, pda, L-system etc etc. Go to http://www.cs.duke.edu/~rodger/tools/jflap/


• These next two items are very good, but they contain a lot more than you need for this course. Arto Salomaa: Computation and Automata. Encyclopædia of mathematics and its applications. CUP 1985


• John E Hopcroft and Jeffrey D Ullman. Introduction to Automata Theory, Languages and Computation. Addison-Wesley