Introduction to Theoretical Computer Science

Course Description

The course introduces formal models of automata and grammars used for description, definition, software and hardware implementation, as well as verification of correctness of execution of computer and communication processes, protocols, and systems. Basic properties of computing processes and systems, such as determinism, decidability, computability, complexity, and tractability, are explained. Basics of automata theory, formal grammars, and languages are given. Chomsky hierarchy of languages is presented: regular languages, context-free languages, context-sensitive languages, recursive languages, and recursively-enumerable languages. Complexity classes and hierarchy of complexity classes are defined: complete and hard problems, polynomial classes P and NP, and reduction method.

General Competencies

The course prepares the students for application of formal models in engineering for the design of computer and communication processes, protocols, and systems. Based on the problem definition, students will be able to construct the formal model of the proposed solution, validate its correctness, estimate its efficiency and complexity, implement it in software or hardware, as well as document and test it. Furthermore, students acquire solid fundamental knowledge that is the basis for further study of theory of complex computing processes and systems.

Learning Outcomes

  1. model the behavior of a computer system and communication protocol using formal language
  2. design a computing process using a formal model
  3. apply formal models to verify the corectness of a computer system
  4. categorize a problem with respect to Chomsky hierarchy of formal languages
  5. select the optimal formal model for description, design, and implementation of a computer system
  6. estimate time and space complexity of a computing process
  7. evaluate the efficiency of a computer system and communication protocol

Forms of Teaching

Lectures

Lecturer-driven classroom presentations, examples of practical application of formal languages, automata, and grammars

Exams

Two written exams

Exercises

Lecturer-driven classroom problem solving, preparation for written exams

Laboratory Work

Implementation of algorithms on formal languages, automata, and grammars. Application of automata and grammars in practical software development. Online submission and evaluation of student work.

Consultations

Individual office hours with lecturers and assistants are organized on student's request.

Grading Method

Continuous Assessment Exam
Type Threshold Percent of Grade Threshold Percent of Grade
Laboratory Exercises 50 % 30 % 50 % 0 %
Class participation 0 % 5 % 0 % 0 %
Mid Term Exam: Written 0 % 35 % 0 %
Final Exam: Written 0 % 35 %
Exam: Written 50 % 100 %
Comment:

Continuous Assessment: Min (Mid Term Exam: Written + Final Exam: Written + Lecture attendance and oral examination in classroom) = 50 %

Week by Week Schedule

  1. Symbol, alphabet, string, and formal language; Example of formal language, automata, and grammar; ([1], pp. 1-14) Deterministic finite automata: example and definition; Deterministic finite automata: implementation and minimization; ([1], pp. 15-29)
  2. Determinism and nondeterminism; Nondeterministic finite automata; Nondeterministic finite automata with e-moves; ([1], pp. 29-39) Finite automata with output; Regular expressions; Finite automata generator; ([1], pp. 39-51)
  3. Properties of regular sets; Formal grammar: example and definition; Regular grammar; ([1], pp. 51-63) Regular grammar (continuation); Context-free languages; Context-free grammar; Grammar and language ambiguity; Simplification of context-free grammars; ([1], pp. 63-78)
  4. Simplification of context-free grammars (continuation); ([1], pp. 78-88) String derivation and parsing; Implementation of top-down parsing; Recursive-descent parsing; Bottom-up parsing; LR parsing; ([1], pp. 89-102)
  5. Pushdown automata: example and definition; ([1], pp. 103-114) Pushdown automata (continuation); Properties of context-free languages; ([1], pp. 114-125)
  6. Exercises: regular languages;
  7. Exercises: context-free languages;
  8. First mid term exam: regular languages, context-free languages;
  9. Recursively-enumerable languages; Turing machine; Techniques for constructing Turing machine; ([1], pp. 126-138) Generalization of basic Turing machine model; ([1], pp. 139-146)
  10. Restriction of basic Turing machine model; Turing machine based language generation; ([1], pp. 146-151) Unrestricted grammar; Properties of recursive and recursively-enumerable languages; Computability; Decidability; ([1], pp. 152-164)
  11. Context-sensitive languages; Context-sensitive grammar; Linear bounded automata; Properties of context-sensitive languages; ([1], pp. 165-172) Properties of context-sensitive languages (continuation); Chomsky hierarchy of formal languages, grammars, and automata; Definitions of space and time complexity; Complexity of automata and languages; Properties of space and time complexity functions; ([1], pp. 173-187)
  12. Complexity classes; ([1], pp. 187-190) Complexity properties of hierarchy of languages; ([1], pp. 190-194)
  13. Polynomial complexity classes; Tractability; Reduction method; Definition of complete and hard problems; P-complete (hard) and NP-complete (hard) problems; ([1], pp. 194-199)
  14. Exercises: recursively-enumerable languages, context-sensitive languages, complexity theory;
  15. Final exam: whole course matter;

Study Programmes

University undergraduate
Computing (study)
(4. semester)

Literature

S. Srbljić (2007.), Uvod u teoriju računarstva, Element Zagreb
J. Hromkovic (2003.), Theoretical Computer Science: Introduction to Automata, Computability, Complexity, Algorithmics, Randomization, Communication, and Cryptography, Springer
J. E. Hopcroft, R. Motwani, J. D. Ullman (2000.), Introduction to Automata Theory, Languages, and Computation, Addison-Wesley
P. Linz (2000.), An Introduction to Formal Languages and Automata, Jones & Bartlett Publishers
D. C. Kozen (1997.), Automata and Computability, Springer

Lecturers

Exercises

Laboratory exercises