Course Details
Course Information Package
Course Unit Title | THEORY OF COMPUTATION | ||||||||
Course Unit Code | ACSC301 | ||||||||
Course Unit Details | BSc Computer Science (Required Courses) - | ||||||||
Number of ECTS credits allocated | 5 | ||||||||
Learning Outcomes of the course unit | By the end of the course, the students should be able to:
| ||||||||
Mode of Delivery | Face-to-face | ||||||||
Prerequisites | ACSC191 | Co-requisites | NONE | ||||||
Recommended optional program components | NONE | ||||||||
Course Contents | Introduction to Automata Theory: Introduction to Finite Automata; Structural representations; Automata and complexity; Central concepts of Automata Theory: alphabets, strings, languages, problems. Finite Automata: Informal view of Finite Automata; Deterministic Finite Automata; DFA notation; DFA transition function; The language of a DFA; Nondeterministic Finite Automata; NFA transition function; DFA and NFA equivalence; Finite Automata with epsilon transitions; Epsilon-closures; DFA and Epsilon NFA equivalence.
Regular Expressions and Languages: Operators of Regular Expressions; Building Regular Expressions; Precedence of operators; Converting DFA’s to Regular Expressions; Converting Regular Expressions to Automata; Applications of Regular Expressions; Algebraic laws of Regular Expressions.
Properties of Regular Languages: Proving languages not to be regular; Closure properties of Regular Languages; Decision properties of Regular Languages.
Context-Free Grammars and Languages: Definition of Context-Free Grammars; Derivations using a grammar; Language of a grammar; Sentential forms; Constructing parse trees; Inference, derivations and parse trees; From inferences to trees; From trees to derivations; from derivations to recursive inferences; Applications of CFG’s; Ambiguity in Grammars and Languages.
Pushdown Automata: Definition of Pushdown Automata; Graphical notation for PDA’s; Instantaneous descriptions of a PDA; Languages of a PDA; From CFG’s to PDA’s; From PDA’s to CFG’s; Deterministic PDA’s.
Properties of Context-Free Grammars: Normal forms of CFG’s; The pumping lemma for CFG’s; Closure properties of CFG’s; Decision properties of CFG’s.
Turing Machines: Turing Machine notation; Instantaneous descriptions of TM’s; Transition diagrams for TM’s; The language of a TM; TM’s and Halting; Programming techniques for TM’s. Undecidability: The halting problem; Reducing one problem to another; A language that is not recursively enumerable; Recursive languages; Complements of recursive and RE languages; The universal language; Undecidability of the universal language; Undecidable problems about TM’s; Post’s correspondence problem. | ||||||||
Recommended and/or required reading: | |||||||||
Textbooks |
| ||||||||
References |
| ||||||||
Planned learning activities and teaching methods | The course is delivered through three hours of lectures per week, which include presentation of new material and demonstration of concepts. Lectures also include in-class exercises to enhance the material learning process and to assess the student level of understanding and provide feedback accordingly. | ||||||||
Assessment methods and criteria |
| ||||||||
Language of instruction | English | ||||||||
Work placement(s) | NO |