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 2020-21 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) Be familiar with the relationships between language as an object recognised by an automaton and as a set generated by a formal grammar.

(LO2) Be able to apply standard translations between non-deterministic and deterministic finite automata.

(LO3) Be familiar with the distinct types of formal grammar (e.g. Chomsky hierarchy) and the concept of normal forms for grammars.

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

(LO5) Understand the distinction between recursive and recursively enumerable 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, minimization of automata.
Context-free grammars: introduction, derivation trees, simplification, Chomsky normal form, Greibach normal form.
Pushdown automata: definitions, shared properties with context-free grammars.
Properties of context-free grammars: pumping lemma, closure properties and decision algorithm.
Chomsky hierarchy and deterministic context-free languages: normal form, closure, and application in parsing methods.
Turing machines: Turing machine model, computable languages and functions, Church's hypothesis.
Undecidability: recursive and recursively enumerable languages, universal Turing machines.

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 2020/21, one or more of the following delivery methods will be implemented based on the current local conditions.
(a) Hybrid delivery, with social distancing on Campus
Teaching Method 1 - Lecture
Description: On-line asynchronous lectures
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 asynchronous lectures
Teaching Method 2 - Tutorial
Description: On-line synchronous/asynchronous sessions

(c) Standard on-campus delivery with minimal social distancing.
As our planning has already gone too far, even if the campus opens up, we will offer hybrid teaching
Teaching Method 1 - Lecture
Description: On-line asynchronous lectures
Teaching Method 2 - Tutorial
Description: Mix of on-campus/on-line synchronous/asynchronous 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 3 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. Assessment Schedule (When) :2  1 hour    15       
(218.2) Assessment 2 Standard UoL penalty applies for late submission. Assessment Schedule (When) :2  1 hour    15       

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