Module Specification
The information contained in this module specification was correct at the time of publication but may be subject to change, either during the session because of unforeseen circumstances, or following review of the module at the end of the session. Queries about the module should be directed to the member of staff with responsibility for the module.
1. Module Title Introduction to Theory of Computation
2. Module Code COMP218
3. Year Session 2023-24
4. Originating Department Computer Science
5. Faculty Fac of Science & Engineering
6. Semester First Semester
7. CATS Level Level 5 FHEQ
8. CATS Value 15
9. Member of staff with responsibility for the module
Dr DK Wojtczak Computer Science D.Wojtczak@liverpool.ac.uk
10. Module Moderator
11. Other Contributing Departments  
12. Other Staff Teaching on this Module
Mrs J Birtall School of Electrical Engineering, Electronics and Computer Science Judith.Birtall@liverpool.ac.uk
13. Board of Studies
14. Mode of Delivery
15. Location Main Liverpool City Campus
    Lectures Seminars Tutorials Lab Practicals Fieldwork Placement Other TOTAL
16. Study Hours 28

   10

     2

 40
17.

Private Study

 110
18.

TOTAL HOURS

 150
 
    Lectures Seminars Tutorials Lab Practicals Fieldwork Placement Other
19. Timetable (if known)            
 
20. Pre-requisites before taking this module (other modules and/or general educational/academic requirements):

 
21. Modules for which this module is a pre-requisite:

 
22. Co-requisite modules:

 
23. Linked Modules:

 
24. Programme(s) (including Year of Study) to which this module is available on a mandatory basis:
25. Programme(s) (including Year of Study) to which this module is available on a required basis:
26. Programme(s) (including Year of Study) to which this module is available on an optional basis:
27. Aims
 

To introduce formal concepts of automata, grammars and languages.
To introduce ideas of computability and decidability.
To illustrate the importance of automata, formal language theory and general models of computation in Computer Science and Artificial Intelligence.
 
28. Learning Outcomes
 

(LO1) Define the relationship between language as an object recognised by an automaton and as a set of words generated by a formal grammar.
 

(LO2) Apply standard translations between different models of computation.
 

(LO3) Discuss the distinct types of formal grammar (e.g. Chomsky hierarchy) and the concept of normal form for grammars.
 

(LO4) Illustrate the limitations (with respect to expressive power) of different automata and grammar forms.
 

(LO5) Explain the difference between decidable and recognisable languages.
 

(S1) Numeracy/computational skills - Reason with numbers/mathematical concepts
 

(S2) Numeracy/computational skills - Problem solving
 

(S3) Information skills - Information accessing:[Locating relevant information] [Identifying and evaluating information sources]
 
29. Teaching and Learning Strategies
 

Teaching Method 1 - Lecture
Description:
Attendance Recorded: Not yet decided

Teaching Method 2 - Tutorial
Description:
Attendance Recorded: Not yet decided

Teaching Method 3 - Assessment
Description:
Attendance Recorded: Not yet decided

Standard on-campus delivery
Teaching Method 1 - Lecture
Description: Mix of on-campus/on-line synchronous/asynchronous sessions
Teaching Method 2 - Tutorial
Description: On-campus synchronous sessions
 
30. Syllabus
   

Preliminaries: principal mathematical ideas necessary to understand the material of the course.
Finite automata and regular expressions: basic definitions, non-determinism, applications of finite automata.
Properties of regular sets: pumping lemma, closure properties, decision algorithms, minimisation of automata.
Context-free grammars: introduction, derivations, parse trees, Chomsky normal form.
Pushdown automata: definitions, shared properties with context-free grammars.
Properties of context-free grammars: pumping lemma, closure properties and parsing algorithms.
Turing machines: Turing machine model, decidable languages, Church-Turing thesis.
Undeciadability: universal Turing machines, undecidable problems, reducibility.
Chomsky hierarchy: context-sensitive, recognisable and unrecognisable languages.
 
31. Recommended Texts
  Reading lists are managed at readinglists.liverpool.ac.uk. Click here to access the reading lists for this module.
 

Assessment
32. EXAM Duration Timing
(Semester)		 % of
final
mark		 Resit/resubmission
opportunity		 Penalty for late
submission		 Notes
  (218) Written Exam There is a resit opportunity. 0 70
33. CONTINUOUS Duration Timing
(Semester)		 % of
final
mark		 Resit/resubmission
opportunity		 Penalty for late
submission		 Notes
  (218.1) Class Test 1 Standard UoL penalty applies for late submission. 0 10
  (218.2) Class Test 2 Standard UoL penalty applies for late submission. 0 10
  (218.3) Assessment 3 Standard UoL penalty applies for late submission. 0 10