Pre-requisites, Textbook, Course Objectives and outcomes
Pre-requisites: Computer Architecture, Discrete Mathematical Structures
Textbook & Reference: Theory of Computation: Automata, Formal Languages, Computation, and Complexity
Course objectives
To understand the concept of machines: finite automata, push down automata, linear bounded automata, and Turing machines.
To understand the formal languages and grammars: regular, context-free, and context-sensitive, and unrestricted.
To understand the relation between languages, grammars, and machines.
To understand the difficulty level of problems when solved on these machines.
To understand the concept of algorithm, and 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;
-> analyze a given Finite Automata machine and find out its Language;
-> design Push down Automata machine for given CF language(s);
-> generate the strings/sentences of a given context-free languages;
-> design Turing machines for given any computational problem.
Deployment of the course
Deployment of the course: CS222Module 1: Finite Automata & Regular Languages
The FA is simplest machine/model of computation, that recognize regular languages -- language of tokens.
The language of tokens is pattern language, and can be represented by regular expressions (RE) -- compact representation. The REs can generate non-deterministic FA, which after converting into deterministic finite automata, can recognize reg. languages.
The FA 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 (CF), Grammars & Pushdown Automata
All the present high level languages, like, C, C++, Java, etc falls in the class of CF languages. The CF are generated using CF grammars, through parsing.
This module covers following:
Relation between Regular language and CF, Regular Grammar and CF grammar, and closure properties of CF languages.
The ambiguities in CFL and CFG, and how to remove them.
Pumping lemma for CF languages: Using this one can test a language property and show that it does not belong to the class of CF.
Complexity analysis of CFL and problem solutions.
Transformations of CFL are proved to show that when null, unit, and useless productions are removed the generating power of CFG rmains unchanged.
Normalization, Chomsky Normal Form (CNF), Greibach Normal Form (GNF), and show that grammars' power remains the same.
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