PMA 1050 / PMA 6853: Discrete Foundations 2004-5

by Dr. P.G. Dixon

IMPORTANT: This is not the current web page for this course.  The current web page is  http://www.dcs.shef.ac.uk/~pdg/PMA1050.

The purpose of this page is merely to provide an archive copy of the web page I had when I was giving the course, but without the questions and solutions, which may be being used by the current lecturer.    Any queries about the course should be addressed to the current lecturer, Dr. V. V. Bavula: e-mail  V.Bavula  with the usual extension  @sheffield.ac.uk

This 10-credit half-module explores the theoretical foundations of Computer Science, answering the question: "What is computation?". It introduces the discrete mathematical modelling techniques needed to describe software systems, construct specifications and prove that they are correct. Topics covered include: sets, functions and relations; propositional logic, truth tables and rules of inference; simple proof, refutation proof and inductive proof; finite automata, regular expressions, Moore and Mealy machines; phrase structure grammars, regular and context-free languages.

Aims of the Course

• to establish a link between computational problems and precise formal models
• to provide a grounding in set theory and propositional logic
• to provide a grounding in natural deduction, refutation and inductive proof techniques
• to develop an understanding of abstract automata, grammars and formal languages
• to prepare students for advanced theory courses at higher levels

Course organization

The course is three lectures/problem classes per week in the first semester. Homework will be set at the last session each week and solutions presented the following week.

Assessment

• PMA1050: One two-hour examination: candidates will be asked to answer 3 questions out of 4. Pass mark 40%.
• PMA6853: One two-hour examination: candidates will be asked to answer Question 1, and 2 questions out of the remaining 3. Question 1 will be a deeper question covering a variety of topics from throughout the syllabus. Pass mark 50%.

For both papers, all the material in the lecture notes is examinable except for the definition of context sensitive grammar and the final section, from the heading `Pushdown Automata' to the end.

Past Papers

Here are the January 2004 COM1050 paper and solutions, and the January 2004 COM6853 paper and solutions.

Here is the January 2003 COM1050 exam paper, adjusted for the notation used this year: solutions are not available.

Here is a hypothetical January 2003 COM6853 exam paper.  This was produced in the format, described above, of this session's COM6853 exam, using the January 2003 COM1050 paper and questions set during the course. 

Prerequisites and Corequisites

Co-requisite: basic knowledge of programming, from COM1010.

Intended Learning Outcomes

• be able to develop and analyse simple discrete models of computer systems;
• be able to use set theory and propositional logic with confidence;
• be able to prove mathematical properties by refutation and by induction;
• understand the properties of automata and their associated languages and grammars.

Course content

• Set theory: [ 2 lectures ]
• Theory of Functions: [ 2 lectures ]
• Methods of Proof: [ 2 lectures ]
• Induction and Recursion: [ 2 lectures ]
• Propositional Logic: [ 2 lectures ]
• Finite Automata: [3 lectures ]
• Kleene's Theorem: [ 1 lecture]
• Mealy Machines: [ 2 lectures ]
• Formal Languages and Grammars: [ 2 lectures ]
• Regular Grammars and Regular Languages: [ 2 lectures ]

Recommended Books

1. J. Gersting, Mathematical Structures for Computer Science.
2. M. Piff, Discrete Mathematics, (Cambridge University Press, 1991).
3. D. I. A. Cohen, Introduction to Computer Theory, (Wiley, 1991).

More advanced books for background reading

1. J. Carroll and D. Long, Theory of finite automata with an introduction to formal languages (Prentice-Hall, 1989).
2. John E. Hopcroft and Jeffrey D. Ullman, Introduction to Automata Theory, Languages and Computation (Addison-Wesley, 1979)

Online Resources

• The site http://www.geocities.com/basicmathsets/ gives an introduction to sets at a very basic level. It covers elements of sets, subsets, unions and intersection, but not much more, but it does go very slowly and it gives you random exercises and marks them. Very useful if you have never met sets before.
• These notes by David Wagner for a Discrete Mathematics for Computer Science course at Berkeley have a nice chapter on induction.
• This is a page of links connected with George Boole, the founder of Boolean algebra.
• These lecture notes by Steve Sugden for a course on Discrete Mathematics look useful, but note that he uses + and . for AND and OR in the propositional calculus.
• This  Mathematics for Computer Scientists course by Thorsten Altenkirch at Nottingham has some nice examples of truth tables.
• Nicolas Christin has a delightful deterministic finite automata applet simulator which enables you to design your own finite automaton and then run it with various inputs; read the documentation carefully first.
• This document describes Moore and Mealy machines with a view to implementation in logic circuits.
• The Java Language Specification provides a good illustration of the use of formal grammars in specifying programming language syntax.
• This page from the University of Geneva presents the syntax of several programming languages in Backus-Naur Form.
• Another BNF specification for Java is shown here.

Lecture slides

The links in this section are currently disabled.

The question sheets and solutions are posted below. Hard copy will be distributed.

• Sheet 1: questions and solutions.
• Sheet 2: questions and solutions.
• Sheet 3 onwards: questions and solutions.
• Multiple Choice Test 1 and the blank answer sheet.

Reading Week 

There will be a reading week for this course in week 7. In this week there will be no formal lectures and no further homework set. There will be optional help sessions that week.  Details of these will be given nearer the time.