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
understand the concept of machines: Finite Automata, Pushdown Automata, Linear Bounded Automata, and Turing Machines.
understand the formal languages and grammars: regular, context-free, and context-sensitive, and unrestricted.
understand the relation between languages, grammars, and machines.
understand the difficulty level of problems when solved on these machines.
understand the concept of algorithm, and compare the complexity of problems.
Course Outcomes
On having 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;
generate 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 high level languages, like, C, C++, Java, etc., falls in the class of CF languages. The CFLs are generated by CFGs.
This module covers:
Relation between Regular and CF languages, Regular and CF grammars, and closure properties of CF languages.
The ambiguities in CFL and CFG, and how to remove them.
Pumping Lemma for CF languages. and uisng it to show that a language does not belong to the class of CFLs.
Complexity analysis of CFL.
Transformations of CFL are proved to show that when null, unit, and useless productions are removed, the generating power of CFG remains the same.
Normalization: Chomsky Normal Form (CNF), Greibach Normal Form (GNF). Show that normalized 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.
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 only from 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 equal number of times.
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