Pre-requisites, Course Objectives and outcomes
Pre-requisites: Computer Architecture, Fundamentals of Discrete Mathematical Structures III Edition (With GATE Problems), ISBN: 978-81-203-5074-8
Course objectives
To understand the concept of machines: finite automata, pushdown automata, linear bounded automata, and Turing machines.
To understand the formal languages and grammars: regular grammar and regular languages, context-free languages and context-free grammar; and introduction to context-sensitive language and context-free grammar, and unrestricted grammar and languages.
To understand the relation between these formal languages, grammars, and machines.
To understand the complexity or difficulty level of problems when solved using these machines.
To understand the concept of algorithm.
To compare the complexity of problems.
Course Outcomes
Once the student has undergone the course of Theory of Computation, and met the requirements of assignments, midterm and end-term examination, she/he will be:
-> able to design Finite Automata machines for given problems;
-> able to analyze a given Finite Automata machine and find out its Language;
-> able to design Pushdown Automata machine for given CF language(s);
-> able to generate the strings/sentences of a given context-free languages using its grammar;
-> able to design Turing machines for given any computational problem.
Module 1: Finite Automata & Regular Languages
The finite automata (FA)is simplest machine/model of computation, that recognize regular languages, also called the language of tokens.
The language of tokens or elementary strings, is pattern language and can be represented by regular expressions, which is compact form of representation. The regular expressions can be used to generate non-deterministic FA, which after converting into deterministic finite automata, can recognize regular language or tokens.
The Finite Automata can be minimized to reduce the number of states in it, making is more efficient or fast. The minimization can be done using the Myhill-Nerode Theorem.
A language can be finite or infinite. The pumping lemma can be used to test a language for its non-regularity.
Module 2: Context-free Languages, Grammars & Pushdown Automata
All the present high level languages, like, C, C++, Java, etc falls in the class of context-free languages. The context-free languages are generated using context-free grammars, through the process of parsing.
This module covers following:
Relation between Regular language and context-free language, Regular Grammar and Context-free grammar, and various closure properties of context-free languages.
The ambiguities in CFL and CFG, and how the ambiguities can be removed in some of the cases.
Pumping lemma for context-free languages: Using this one can test a language property and show that is does not belong to the class of context-free. (To show the property of non-context-free.
In addition, the complexity analysis of CFL and problem solutions are discussed.
Various transformations of CFL as explained and proved, to show that if null-production, unit productions, and useless productions are removed from a given CFG, its generating power remains the same.
The process of normalization, using Chomsky Normal Form (CNF) or Greibach Normal Form (GNF) transform a grammar into standard form, but keep its generating power remains unchanged.
The CNF and GNF are simplified grammars, and they have some properties that are useful in theorem proving and drawing many useful conclusions.
The PDA (Pushdown Automata) is a machine, which is like finite automata, and has in addition, a push-down store, called stack. The stack can read/write, but from only one side, i.e., its top.
The PDA can recognize the CFL. For example, to recognize a^nb^n, it can push a, total n tines, and can compare by popping with bs.
Module 3: Turing Machine, Chomsky Hierarchy, Complexity Theory
The Turing machine is ultimate computing model, as it recognizes all the 4 classes of languages as well it can compute every thing that can be computed using any algorithm.
This module covers the topics of Turing machine as language recognizer, and Turing machine as a computing machine.
Variants of Turing machine, i.e., Turing machine with multi-tape, multi-track, multi-dimension tape, non-deterministic Turing machines, and Universal Turing machine, are covered.
All these Turing machines show that, ultimately they are equal to standard TM. hence, the standard TM is ultimate model of Computation.
The Universal Turing machine has been demonstrated to simulate a standard TM, with the help of a 3-tape TM in Univ. TM
The Chomsky hierarchy is set of grammars, languages, and machines, with set-subset relation. Grammar types are 3, 2, 1, 0 for regular, context-free, context-sensitive, and unrestricted. Corresponding languages also. The machines in order are: TM, LBA, PDA, and FA.
The languages recognized by TM are called Recursively Enumerable (RE)) language, which are also called Turing recognizable languages, and these are semi-decidable language. The Recursive languages are decidable, and the corresponding TM always halts.
There are problems about which we cannot decide, there are languages whose membership cannot be decided, and there are questions about which neither we can say yes nor no. Such problems are called undecidable problems.
How much difficult a problem is, is called its complexity, which may be in terms of time needed to solve it, or space needed by it. These computations about complexities are done with reference to Turing Machine.
The important complexity classes are NP, NP-complete, and NP-hard