BSc in Computer Science / Бакалавр в Области Компьютерных Наук

Course Details

Course Information Package

Course Unit TitleTHEORY OF COMPUTATION
Course Unit CodeACSC301
Course Unit DetailsBSc Computer Science (Required Courses) -
Number of ECTS credits allocated5
Learning Outcomes of the course unitBy the end of the course, the students should be able to:
  1. Describe in detail what is meant by a finite state automaton, a push-down automaton, a grammar and a Turing Machine.
  2. Work out and illustrate the behaviour of a given example of these machines.
  3. Design a machine of this type corresponding to a particular language.
  4. Reason about the capabilities of such machines and demonstrate that they have limitations.
  5. Describe a decision procedure in terms of a language and define a language by using a grammar.
Mode of DeliveryFace-to-face
PrerequisitesACSC191Co-requisitesNONE
Recommended optional program componentsNONE
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
  • John E. Hopcroft, Rajeev Motwani and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, 3rd Edition, Addison-Wesley, 2006.
References
  • Michael Sipser, Introduction to the theory of computation, 2nd Edition, Thomson Course Technology, 2006.
  • Daniel I. A. Cohen, Introduction to computer theory, 2nd Edition, Wiley, 1997.
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
Assignments20%
Tests20%
Final Exam60%
Language of instructionEnglish
Work placement(s)NO

 Печать  E-mail