- Course description
- Lecture slides and notes
- Tutorial Exercises
- General Information & Other Resources
2a. Aims and Objectives
The goal of this course is to introduce you to computational thinking —
using computational models to describe and reason about systems that change
through time. We focus on finite-state systems and propositional logic.
Finite state machines provide a simple model of computation
that is widely used, has an interesting meta-theory and has immediate
application in a range of situations. They provide an essential underpinning
for your future study of more general computational models, across the whole of Informatics.
Propositional logic, is used to describe and reason about finite state systems.
It provides a basis for later study of more general logics used to specify and reason about
This course provides students with experience of theory
in practical applications. An unordered list of topics is as follows:
- Informatics looks at the world in terms of information.
Nature is, perhaps, infinitely complicated, but we often use
abstract models of natural systems based on a finite amount of information.
The first part of this course deals with such models, how we can speak about the
states of such systems, using propositional logic.
For example, a weather report describes
the state of the weather by reporting a finite number of attributes.
The philosophers have only interpreted the world, in various ways; the point is to change it.
In the second part of the course we model change. Many systems in nature change continuously.
Our second abstraction is to consider a discrete series of time steps, and to focus on how the state of our system changes from one step to another, without worrying about the details of what happens in between.
For example, in describing a game of chess we focus on the state of the board before and after each move, but pay no attention to the way the players move their pieces.
- A brief introduction of computation as a process and a method of
modelling behaviour. Discussion of the advantages of moving to simple
models that are appropriate for restricted classes of tasks.
Discussion of the importance of correctness of computational
procedures, and how logic can be used to reason about correctness.
- Reasoning: Propositional logic, its connectives and the meaning
of those connectives in terms of truth tables. The concepts of
satisfiability, validity and proof. The relationship between a
proof and the validity of an implication in terms of truth tables.
- Computation: the definition as acceptor and transducer,
deterministic/non deterministic machines, regular
expressions, operations on FSMs,
discussion of formal limits, how good are FSMs as a model of
- Applications/Modelling: simple examples drawn from a number of
domains, design issues, using operations on FSMs to structure
solutions, more complex examples: dialogue systems, controllers,
digital watch, regular expressions and pattern matching. Application
areas such as robotic controllers.
- Engineering: how do we specify, test and debug FSM's, design by
decomposition, concurrency, size of machines.
- Using Logic to describe change. The Stanford Research Institute Problem Solver (STRIPS) and elementary planning.
- Tools: examples of logic/FSM based tools in system building.
The main reference for this course is Foundations of Computer Science by Aho and Ullman.
This book has been taken out of print by W. H. Freeman. You may be lucky and find a used copy,
e.g. on Amazon,
but it is freely available for download on the web :-)
As a secondary reference, I suggest you purchase Kozen's
Automata and Computability.
The second half of the course will follow Kozen quite closely.
Although you will only be using the first 50 pages or so for this course,
this book is also used in Inf2.
This course supplies foundational knowledge for Informatics courses
taken in subsequent years of study. It runs alongside the Informatics
1 Functional Programming course, which provides complementary
experience in programming.
3b. Finite State Machines
- FSM notes:
- Lecture slides:
You can find your tutorial group at Informatics Theon Portal
times, locations, tutor and student lists are provided. Tutorial exercise solutions will be released after the appropriate tutorials have been held.
There is a single assignment for Computation and Logic. It does not
count toward your final mark for the course but it is a course
requirement that you complete it, and it will be assessed to provide
feedback for your benefit.
The following assignment is due for submission to the
Informatics Teaching Organisation (level 4 of Appleton Tower) by
noon 15th of November. [Assignment]
Guide to Standard Answers (and Marking Scheme) [Answers]new!
Past papers for all Informatics courses and modules, organised by year. Search through each year to find available Inf1 Computation and Logic past papers.
Wikipedia is a good
source for many topics, such as,
- Click here
for Matt Chapman's Finite State Machine animator.
This is a Java Applet that allows you to draw FSMs in a window and
experiment with them.
- There is no need for a text book for this course, but those who are interested in more reading can see the following books:
Computation: "An introduction to formal languages and automata" by Peter Linz.
Logic: "The essence of Logic", John Kelly, 1997.
if you still want to read more on logic: "Logic for computer science", Steve Reeves, 1990.