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 Decision, Computation and Language
Code COMP218
Coordinator Dr DK Wojtczak
Computer Science
D.Wojtczak@liverpool.ac.uk
Year CATS Level Semester CATS Value
Session 2021-22 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) Assessment 4 There is a resit opportunity. Standard UoL penalty applies for late submission.  2 hours    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.  1 hour    10       
(218.2) Assessment 2 Standard UoL penalty applies for late submission.  1 hour    10       
(218.3) Assessment 3 Standard UoL penalty applies for late submission.  1 hour    10       

Recommended Texts

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