Module Catalogues, Xi'an Jiaotong-Liverpool University   
 
Module Code: CSE203
Module Title: Decision Computation and Language
Module Level: Level 2
Module Credits: 5.00
Academic Year: 2017/18
Semester: SEM1
Originating Department: Computer Science and Software Engineering
Pre-requisites: N/A
   
Aims
1. To introduce formal concepts of automata, grammars and languages.
2. To introduce ideas of computability and decidability.
3. To illustrate the importance of automata, formal language theory and general models of computation in Computer Science and Artificial Intelligence.
Learning outcomes 
At the end of the module student should:

1.Be familiar with the relationships between language as an object recognised by an automaton and as a set generated by a formal grammar.

2.Be able to apply standard translations between non-deterministic and deterministic automata.

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

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

5.Understand the distinction between decidable and partially decidable languages.Recognise the significance of the Church-Turing hypothesis and its implications
Method of teaching and learning 
Students will be expected to attend three hours of formal lectures as well as to participate in one hour of supervised problem classes in a typical week. Lectures will introduce students to the academic content and practical skills which are the subject of the module, while problem classes will allow students to practice those skills.
In addition, students will be expected to devote six hours of unsupervised time to solving continuous assessment tasks and private study. Private study will provide time for reflection and consideration of lecture material and background reading.
Continuous assessment will be used to test to what extent practical skills have been learnt.
Syllabus 
Preliminaries: principal mathematical ideas necessary to understand the material of the course (3 lectures)
Finite automata and regular expressions: basic definitions,non-determinism, applications of finite automata (4 lectures)
Properties of regular sets: pumping lemma, closure properties,decision algorithms, minimization of automata (6 lectures)
Context-free grammars: introduction, derivation trees,simplification, Chomsky normal form, Greibach normal form (5 lectures)
Pushdown automata: definitions, shared properties with context-free grammars (4 lectures)
Properties of context-free grammars: pumping lemma, closure properties and decision algorithm (4 lectures)
Chomsky hierarchy and deterministic context-free languages: normal form, closure, and application in parsing methods (6 lectures)
Turing machines: Turing machine model, computable languages and functions, Church's hypothesis (6 lectures)
Undecidability: recursive and recursively enumerable languages,universal Turing machines (4 lectures)
Lectures 1-3 Preliminaries
Principal mathematical ideas necessary to understand the material of the course
Lectures 4-7 Finite automata and regular expressions
Finite automata and regular expressions: basic definitions,non-determinism, applications of finite automata
Lectures 8-13 Properties of regular sets
Properties of regular sets: pumping lemma, closure properties,decision algorithms, minimization of automata
Lectures 14-18 Context-free grammars
Context-free grammars: introduction, derivation trees,simplification, Chomsky normal form, Greibach normal form
Lectures 19-22 Pushdown automata
Pushdown automata: definitions, shared properties with context-free grammars
Lectures 23-26 Properties of context-free grammars
Properties of context-free grammars: pumping lemma, closure properties and decision algorithm
Delivery Hours  
Lectures Seminars Tutorials Lab/Prcaticals Fieldwork / Placement Other(Private study) Total
Hours/Semester 56           94  150- 

Assessment

Sequence Method % of Final Mark
1 Written Examination 80.00
2 Assessment Task 10.00
3 Assessment Task 10.00

Module Catalogue generated from SITS CUT-OFF: 10/22/2017 10:36:35 AM