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|
|Recommended optional program components||NONE|
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:|
|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.
All lecture notes and other material is available to students through the course homepage.
|Assessment methods and criteria|
|Language of instruction||English|