### 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 Dr DK Wojtczak Computer Science D.Wojtczak@liverpool.ac.uk Year CATS Level Semester CATS Value Session 2022-23 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

Due to Covid-19, in 2021/22, one or more of the following delivery methods will be implemented based on the current local conditions.

(a) Hybrid delivery
Teaching Method 1 - Lecture
Description: Mix of on-campus/on-line synchronous/asynchronous sessions
Teaching Method 2 -Tutorial
Description: Mix of on-campus/on-line synchronous/asynchronous sessions

(b) Fully online delivery and assessment
Teaching Method 1 - Lecture
Description: On-line synchronous/asynchronous lectures
Teaching Method 2 - Tutorial
Description: On-line synchronous/asynchronous sessions

(c) Standard on-campus delivery
Teaching Method 1 - Lecture
Description: Mix of on-campus/on-l ine 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.    70
CONTINUOUS Duration Timing
(Semester)
% of
final
mark
Resit/resubmission
opportunity
Penalty for late
submission
Notes
(218.1) Assessment 1 Standard UoL penalty applies for late submission.    10
(218.2) Assessment 2 Standard UoL penalty applies for late submission.    10
(218.3) Assessment 3 Standard UoL penalty applies for late submission.    10