Theory of Computation

Course Title: Theory of Computation

Course No: CSC262

Nature of the Course: Theory + Lab

Semester: 4

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 undecidabilty and intractability.

Course Objectives

The main objective of the course is to introduce concepts of the models of computation and formal language approach to computation. The general objectives of this course 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, determine the decidability and intractability of computational problems.

Course Contents

1. Basic Foundations

3 hrs

1.1. Mathematical Foundations

Review of Set Theory, Logic, Functions, Proofs

1.2. Automata, Computability and Complexity

Complexity Theory

Computability Theory

Automata Theory

1.3. Basic Concepts of Automata Theory

Alphabets

Power of Alphabet

Kleen Closure Alphabet

Positive Closure of Alphabet

Strings

Empty String

Substring of a string

Concatenation of strings

Languages

Empty Language

2. Introduction to Finite Automata

8 hrs

2.1. Finite Automata Fundamentals

Introduction to Finite Automata

Introduction of Finite State Machine

2.2. Deterministic and Non-Deterministic Finite Automata

Deterministic Finite Automata (DFA)

Notations for DFA

Language of DFA

Extended Transition Function of DFA

Non-Deterministic Finite Automaton (NFA)

Notations for NFA

Language of NFA

Extended Transition

2.3. Equivalence of DFA and NFA

Equivalence of DFA and NFA

Subset-Construction

Method for reduction of NFA to DFA

Theorems for equivalence of Language accepted by DFA and NFA

2.4. Finite Automaton with Epsilon Transition

Finite Automaton with Epsilon Transition (ε - NFA)

Notations for ε - NFA

Epsilon Closure of a State

Extended Transition Function of ε – NFA

Removing Epsilon Transition using the concept of Epsilon Closure

Equivalence of NFA and ε –NFA

Equivalence of DFA and ε – NFA

2.5. Finite State Machines with Output

Moore machine and Mealy Machines

3. Regular Expressions

6 hrs

3.1. Regular Expressions Fundamentals

Regular Expressions

Regular Operators

Regular Languages and their applications

Algebraic Rules for Regular Expressions

3.2. Equivalence of Regular Expression and Finite Automata

Equivalence of Regular Expression and Finite Automata

Reduction of Regular Expression to ε – NFA

Conversion of DFA to Regular Expression

3.3. Properties of Regular Languages

Properties of Regular Languages

Pumping Lemma

Application of Pumping Lemma

Closure Properties of Regular Languages over (Union, Intersection, Complement)

Minimization of Finite State Machines: Table Filling Algorithm

4. Context Free Grammar

9 hrs

4.1. Context Free Grammar Fundamentals

Introduction to Context Free Grammar (CFG)

Components of CFG

Use of CFG

Context Free Language (CFL)

4.2. Derivations and Parse Trees

Types of derivations: Bottomup and Topdown approach

Leftmost and Rightmost

Language of a grammar

Parse tree and its construction

Ambiguous grammar

Use of parse tree to show ambiguity in grammar

4.3. Regular Grammars

Regular Grammars: Right Linear and Left Linear

Equivalence of regular grammar and finite automata

4.4. Simplification of CFG

Removal of Useless symbols

Nullable Symbols

Unit Productions

Chomsky Normal Form (CNF)

Greibach Normal Form (GNF)

Backus-Naur Form (BNF)

4.5. Context Sensitive Grammar and Properties

Context Sensitive Grammar

Chomsky Hierarchy

Pumping Lemma for CFL

Application of Pumping Lemma

Closure Properties of CFL

5. Push Down Automata

7 hrs

5.1. Push Down Automata Fundamentals

Introduction to Push Down Automata (PDA)

Representation of PDA

Operations of PDA

Move of a PDA

Instantaneous Description for PDA

5.2. Types of PDA and Acceptance

Deterministic PDA

Non Deterministic PDA

Acceptance of strings by PDA

Language of PDA

5.3. PDA Construction and Conversion

Construction of PDA by Final State

Construction of PDA by Empty Stack

Conversion of PDA by Final State to PDA accepting by Empty Stack and vice-versa

Conversion of CFG to PDA

Conversion of PDA to CFG

6. Turing Machines

10 hrs

6.1. Turing Machine Fundamentals

Introduction to Turing Machines (TM)

Notations of Turing Machine

Language of a Turing Machine

Instantaneous Description for Turing Machine

Acceptance of a string by a Turing Machines

6.2. Turing Machine Applications

Turing Machine as a Language Recognizer

Turing Machine as a Computing Function

Turing Machine with Storage in its State

Turing Machine as a enumerator of stings of a language

Turing Machine as Subroutine

6.3. Variants of Turing Machines

Turing Machine with Multiple Tracks

Turing Machine with Multiple Tapes

Equivalence of Multitape-TM and Multitrack-TM

Non-Deterministic Turing Machines

Restricted Turing Machines: With Semi-infinite Tape, Multistack Machines, Counter Machines

6.4. Church Turing Thesis and Universal Turing Machine

Church Turing Thesis

Universal Turing Machine

Turing Machine and Computers

Encoding of Turing Machine

Enumerating Binary Strings

Codes of Turing Machine

Universal Turing Machine for encoding of Turing Machine

7. Undecidability and Intractability

5 hrs

7.1. Computational Complexity

Computational Complexity

Time and Space complexity of A Turing Machine

Intractability

7.2. Complexity Classes and Reducibility

Complexity Classes

Problem and its types: Abstract, Decision, Optimization

Reducibility

Turing Reducible

Circuit Satisfiability

Cook's Theorem

7.3. Undecidability

Undecidability

Undecidable Problems: Post's Correspondence Problem

Halting Problem and its proof

Undecidable Problem about Turing Machines

Laboratory Works

The laboratory work consists of design and implementation of finite state machines like DFA, NFA, PDA, and Turing Machine. Students are highly recommended to construct Tokenizers/Lexers over/for some language. Students are advised to use regex and Perl (for using regular expressions), or any other higher level language for the laboratory works.

1.Design and implement Deterministic Finite Automata (DFA)
2.Design and implement Non-Deterministic Finite Automata (NFA)
3.Implement conversion between DFA, NFA, and ε-NFA
4.Design and implement Push Down Automata (PDA)
5.Design and implement Turing Machines
6.Construct Tokenizers/Lexers using regular expressions

Text Books

1.John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, 3rd Edition, Pearson - Addison-Wesley

Reference Books

1.Harry R. Lewis and Christos H. Papadimitriou, Elements of the Theory of Computation, 2nd Edition, Prentice Hall
2.Michael Sipser, Introduction to the Theory of Computation, 3rd Edition, Thomson Course Technology
3.Efim Kinber, Carl Smith, Theory of Computing: A Gentle introduction, Prentice-Hall
4.John Martin, Introduction to Languages and the Theory of Computation, 3rd Edition, Tata McGraw Hill
5.Kenneth H. Rosen, Discrete Mathematics and its Applications to Computers Science, WCB/Mc-Graw Hill

Notes:

This syllabus follows the official B.Sc. CSIT curriculum of Tribhuvan University. In case of any doubt or revision, the university's published syllabus shall be considered authoritative.

Theory of Computation

Theory of Computation

Select University

Select Program

TabFlux . Theory of Computation . TU . BSC-CSIT