Theory of Computation

Course Title: Theory of Computation

Course No: CSIT.226

Nature of the Course: Theory + Lab

Semester: 4

Full Marks: 60 + 20 + 20

Pass Marks: 24 + 10 + 10

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. The course includes design of Push-down automata and Turing Machines, and covers basics of undecidability and intractability.

Course Objectives

Introduce concepts in automata theory and theory of computation; design different finite state machines; design 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. Unit I: Basic Foundations

3 hrs

1.1. 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, Kleene Closure, Positive Closure of Alphabet, Strings, Empty String, Suffix, Prefix and Substring of a string, Concatenation of strings, Languages, Empty Language, Membership in Language

2. Unit II: Introduction to Finite Automata

8 hrs

2.1. Introduction to Finite Automata, Introduction of Finite State Machine

2.2. Deterministic Finite Automata (DFA), Notations for DFA, Language of DFA, Extended Transition Function of DFA

2.3. Non-Deterministic Finite Automaton (NFA), Notations for NFA, Language of NFA, Extended Transition Function of NFA

2.4. 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.5. Finite Automaton with Epsilon Transition (ε-NFA), Notations, Epsilon Closure of a State, Extended Transition Function of ε-NFA, Removing Epsilon Transition using Epsilon Closure, Equivalence of NFA and ε-NFA, Equivalence of DFA and ε-NFA

2.6. Finite State Machines with output: Moore Machine and Mealy Machine

3. Unit III: Regular Expressions

6 hrs

3.1. Regular Expressions, Regular Operators, Regular Languages and their applications, Algebraic Rules for Regular Expressions

3.2. 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, Pumping Lemma, Application of Pumping Lemma, Closure Properties of Regular Languages over (Union, Intersection, Complement)

3.4. Minimization of Finite State Machines: Table Filling Algorithm

4. Unit IV: Context Free Grammar

9 hrs

4.1. Introduction to Context Free Grammar (CFG), Components of CFG, Use of CFG, Context Free Language (CFL)

4.2. Types of derivations: Bottom-up and Top-down approach, Leftmost and Rightmost, Language of a grammar

4.3. Parse tree and its construction, Ambiguous grammar, Use of parse tree to show ambiguity in grammar

4.4. Regular Grammars: Right Linear and Left Linear, Equivalence of regular grammar and finite automata

4.5. Simplification of CFG: Removal of Useless symbols, Nullable Symbols, and Unit Productions, Chomsky Normal Form (CNF), Greibach Normal Form (GNF), Backus-Naur Form (BNF)

4.6. Context Sensitive Grammar, Chomsky Hierarchy

4.7. Pumping Lemma for CFL, Application of Pumping Lemma, Closure Properties of CFL

5. Unit V: Push Down Automata

7 hrs

5.1. Introduction to Push Down Automata (PDA), Representation of PDA, Operations of PDA, Move of a PDA, Instantaneous Description for PDA

5.2. Deterministic PDA, Non-Deterministic PDA, Acceptance of strings by PDA, Language of PDA

5.3. 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

5.4. Conversion of CFG to PDA, Conversion of PDA to CFG

6. Unit VI: Turing Machines

10 hrs

6.1. 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 Machine

6.2. Turing Machine as a Language Recognizer, Turing Machine as a Computing Function, Turing Machine with Storage in its State, Turing Machine as an enumerator of strings of a language, Turing Machine as Subroutine

6.3. 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, Universal Turing Machine, Turing Machine and Computers

6.5. Encoding of Turing Machine, Enumerating Binary Strings, Codes of Turing Machine, Universal Turing Machine for encoding of Turing Machine

7. Unit VII: Undecidability and Intractability

5 hrs

7.1. Computational Complexity, Time and Space Complexity of a Turing Machine, Intractability

7.2. Complexity Classes, Problem and its types: Abstract, Decision, Optimization

7.3. Reducibility, Turing Reducible, Circuit Satisfiability, Cook's Theorem

7.4. Undecidability, Undecidable Problems: Post's Correspondence Problem, Halting Problem and its proof, Undecidable Problem about Turing Machines

Laboratory Works

Students write programs and prepare lab sheets for most units. Majorly, students practice design and implementation of Finite State Machines viz. DFA, NFA, PDA, and Turing Machine. Students are highly recommended to construct Tokenizers/Lexers for some language. Students are advised to use regex, Perl, C++, Java for using regular expressions. The lab work should be practiced for a minimum of 3 lab hours per week.

1.DFA Design and Implementation
2.NFA Design and NFA to DFA Conversion
3.ε-NFA Design and Epsilon Removal
4.Regular Expressions and Tokenizer/Lexer Construction
5.FSM Minimization
6.Context Free Grammar and Parse Tree
7.CFG Simplification and Normal Forms
8.Push Down Automata (PDA) Design and Implementation
9.Turing Machine Design and Simulation
10.Advanced Turing Machine Variants

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 Computer Science, WCB/McGraw-Hill.

Notes:

This syllabus follows the official CSIT curriculum of Far Western 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 . FWU . BSc. CSIT