Theory of Computation

Home

• Announcements Forum
• Course introduction is here.

  Overview

  Prerequisite

  Following two courses from second year of Computer Engineering are required to be studied:
  

  Discrete MathematicsPrinciples of Programming Languages
  

  Course Objectives

  • To Study abstract computing models
  • To learn Grammar and Turing Machine
  • To learn about the theory of computability and complexity

  Course Outcomes

  On completion of the course, student will be able to:
  

  • Able to design deterministic Turing machine for all inputs and all outputs
  • Able to subdivide problem space based on input subdivision using constraints
  • Able to apply linguistic theory

• Syllabus and Notes

• Unit

  Unit 2

  Unit 3

  Unit 4

  Unit 5

  Unit 6

  Unit

  ×

  Formal Language Theory and Finite Automata

  Introduction to Formal language, introduction to language translation logic, Essentials of translation, Alphabets and languages, Finite representation of language

  Finite Automata (FA): An Informal Picture of FA, Finite State Machine (FSM), Language accepted by FA, Definition of Regular Language, Deterministic and Nondeterministic FA (DFA and NFA), epsilon- NFA

  FA with output: Moore and Mealy machines -Definition, models, inter-conversion. 

  Case Study: FSM for vending machine, spell checker
  

  Close

  Unit 2

  ×

  Regular Expressions (RE)

  Operators of RE, Building RE, Precedence of operators, Algebraic laws for RE

  Conversions: NFA to DFA, RE to DFA Conversions: RE to DFA, DFA to RE Conversions: State/loop elimination

  Arden‘s theorem Properties of Regular Languages: Pumping Lemma for Regular languages, Closure and Decision properties

  Case Study: RE in text search and replace

  Close

  Unit 3

  ×

  Context Free Grammars (CFG) and Languages

  Introduction, Regular Grammar, Context Free Grammar- Definition, Derivation, Language of grammar, sentential form, parse tree, inference, derivation, parse trees, ambiguity in grammar and Language- ambiguous Grammar

  Simplification of CFG: Eliminating unit productions, useless production, useless symbols, and Є-productions, Normal Forms- Chomsky normal form, Greibach normal form, Closure properties of CFL, Decision properties of CFL, Chomsky Hierarchy

  Application of CFG: Parser, Markup languages, XML and Document Type Definitions

  Case Study- CFG for Palindromes, Parenthesis Match
  

  Close

  Unit 4

  ×

  Turing Machines (TM)

  Turing Machine Model, Representation of Turing Machines, Language Acceptability by Turing Machines, Design of TM, Description of TM, Techniques for TM Construction, Variants of Turing Machines, The Model of Linear Bounded Automata , TM & Type 0 grammars, TM‘s Halting Problem
  

  Close

  Unit 5

  ×

  Pushdown Automata (PDA)

  Basic Definitions, Equivalence of Acceptance by Finite State & Empty stack, PDA & Context Free Language, Equivalence of PDA and CFG

  Parsing & PDA: Top-Down Parsing, Top-down Parsing Using Deterministic PDA, Bottom-up Parsing, Closure properties and Deterministic PDA.
  

  Close

  Unit 6

  ×

  Undecidability & Intractable Problems

  A Language that is not recursively enumerable, An un-decidable problem that is RE, Post Correspondence Problem

  The Classes P and NP : Problems Solvable in Polynomial Time, An Example: Kruskal's Algorithm, Nondeterministic Polynomial Time

  An NP Example: The Traveling Salesman Problem, Polynomial-Time Reductions NP Complete Problems

  An NP Complete Problem: The Satisfiability Problem, Tractable and Intractable Representing SAT Instances, NP Completeness of the SAT Problem

  A Restricted Satisfiability Problem: Normal Forms for Boolean Expressions, Converting Expressions to CNF, The Problem of Independent Sets, The Node-Cover Problem
  

  Close
• Previous Years' Exams
  

  Question Papers

  April 2019October 2018April 2018October 2017

• Have Doubts?

• Forum

  Ask your doubts regarding the subject here. Discuss exam strategies, scores and latest trends in this forum.