Tribhuvan University

Institute of Science and Technology

Bachelor of Science in Computer Science and Information Technology

Course Title: Theory of Computation

Course no: CSC257

Semester: V

Nature of course: Theory + Lab

Full Marks: 60 + 20 + 20

Pass Marks: 24 + 8 + 8

Credit Hours: 3

Course Description : This course presents a study of Finite State Machines and their languages. It covers the details of finite state automata, regular expressions, context free grammars. More, the course includes design of the Push-down automata and Turing Machines. The course also includes basics of undecidability and intractability.

Course Objective : The main objective of the course is to introduce concepts of the models of computation and formal language approach to computation. The general objectives are to, introduce concepts in automata theory and theory of computation, design different finite state machines and grammars and recognizers for different formal languages, identify different formal language classes and their relationships, and determine the decidability and intractability of computational problems.

Course Contents:
Laboratory Works:

Student should write programs and prepare lab sheets for most of the units in the syllabus. Majorly, students should practice design and implementation of Finite State Machines viz. DFA, NFA, PDA, and Turing Machine. Students are highly recommended to construct Tokenizers/ Lexical analyzer over/for some language. The nature of programming can be decided by the instructor and students as per their comfort. The instructors have to prepare lab sheets for individual unit covering the concept of all units as per the requirement. The sample lab sessions can be as following descriptions;

Unit I: Basic Foundations (5 Hrs)

  • Write programs for illustrating the concepts of Strings, Prefix, Suffix and Substring of a String.

Unit II & III: Introduction to Finite Automata and Regular Expressions (14 Hrs)

  • Write programs for illustrating the concepts of
    • Determinstic Finite Automata
    • Non-Deterministic Finite Automata
  • Write programs for implementing Tokenizers like for valid C-identifiers, Keywords, e-mail validators, phone number etc.
  • Write programs that implement NFA for text search.
  • Write programs for implementing regular expressions.

Unit IV & V: Context Free Grammar and Push Down Automata (14 Hrs)

  • Write Program for simulation of Leftmost/Rightmost Derivations.
  • Write Program for Parse Tree Contruction.
  • Write programs for illustrating the concepts of context free grammar and its accptance using the concepts of Push Down Automata
    • Acceptance by Final State
    • Acceptance by Empty Stack

Unit VI: Turing Machines (12 Hrs)

  • Write programs for illustrating the concepts of Turing Machine as a Language Recognizer

Reference Books: