Module Details

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.
Title Introduction to Theory of Computation
Code COMP218
Coordinator Professor DK Wojtczak
Computer Science
D.Wojtczak@liverpool.ac.uk
Year CATS Level Semester CATS Value
Session 2024-25 Level 5 FHEQ First Semester 15

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.

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]

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.

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

Teaching Schedule
  Lectures Seminars Tutorials Lab Practicals Fieldwork Placement Other TOTAL
Study Hours 28

   10

     2

 40
Timetable (if known)              
Private Study 110
TOTAL HOURS 150

Assessment
EXAM Duration Timing
(Semester)		 % of
final
mark		 Resit/resubmission
opportunity		 Penalty for late
submission		 Notes
(218) Written Exam There is a resit opportunity.  120    70       
CONTINUOUS Duration Timing
(Semester)		 % of
final
mark		 Resit/resubmission
opportunity		 Penalty for late
submission		 Notes
(218.1) Assessment 3 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) Class Test 1 Standard UoL penalty applies for late submission.  0    10       

Recommended Texts
Reading lists are managed at readinglists.liverpool.ac.uk. Click here to access the reading lists for this module.