Courses--> Computer Science & Engineering -->Theory of Automata and Formal Languages (Video)

Computer Science and Engineering

Theory of Automata and Formal Languages  (Video Course)

IIT Kanpur

Faculty Coordinators




Prof. Somenath Biswas


Department of Computer Science and Engineering
Indian Institute of Technology Kanpur
Kanpur 208016, India
Email : sb@cse.iitk.ac.in
Telephone : (91-512) 259 7574 (Office)
                  (91-512)               (Residence)


                  

Detailed Syllabus


Theory of Automata and Formal Languages

Module 1
(2 Lectures)

Introduction; alphabets, Strings and Languages; automata and Grammars

Module 2
(3 Lectures)

Finite automata (FA) -its behavior; DFA -Formal definition, simplified notations (state transition diagram, transition table), Language of a DFA.

NFA -Formal definition, Language of an NFA, Removing, epsilon-transitions.

Equivalence of DFAs and NFAs

Module 3
(3 Lectures)

Regular expressions (RE) -Definition, FA and RE, RE to FA, FA to RE, algebraic laws for RE, applications of REs.

Regular grammars and FA, FA for regular grammar, Regular grammar for FA

Module 4
(3 Lectures)

Proving languages to be non-regular -Pumping Lenma, applications.

Some closure properties of Regular languages -Closure under Boolean operations, reversal, homomorphism, inverse homomorphism, etc.

M hill-Nerode theorem

Module 5
(3 Lectures)

DFA Minimization

Some decision properties of Regular languages -emptiness, finiteness, membership, equivalence of two DF As or REs, etc. Two-way finite automata, Finite automata with output

Module 6
(3 Lectures)

Context-free Grammars (CFGs) -Formal definition, sentential forms, leftmost and rightmost derivations,, the language of a CFG. Derivation tree or Parse tree -Definition, Relationship between parse trees and derivations.

Parsing and ambiguity, Ambiguity in grammars and Languages

Module 7
(3 Lectures)

Pushdown Automata (PDA) -Formal definition, behavior

and graphical notation, Instantaneous descriptions (Ids), The language of PDA (acceptance by final state and empty stack). Equivalence of acceptance by final state and empty stack,

Equivalence of PDAs and CFGs, CFG to PDA, PDA to CFG.

Module 8
(3 Lectures)

DPDAs -Definition, DPDAs and Regular Languages, DPDAs

and CFLs.

Languages of DPDAs, DPDAs, and ambiguous grammars.

Module 9
(3 Lectures)

Simplification of CFGs -Removing useless symbols, epsilon-

Productions, and unit productions, Normal forms -CNF and GNF

Module 10
(4 Lectures)

Proving that some languages are not context free -Pumping lemma for CFLs, applications.

Some closure properties of CFLs -Closure under union, concatenation, Kleene closure, substitution, homomorphism, reversal, intersection with regular set, etc. Some more decision properties of CFLs, Review of some undecidable CFL problems.

Module 11
(6 Lectures)

Turing Machines TM -Formal definition and behavior,

Transition diagrams, Language of a TM, TM as accepters and deciders.

TM as a computer of integer functions

Programming techniques for TMs -Storage in state, multiple tracks, subroutines, etc.

Variants of TMs -Multitape TMs, Nondeterministic TMs.

TMs with semi-infinite tapes, multistack machines.

Equivalence of the various variants with the basic model

Module 12
(2 Lectures)

Recursive and recursively enumerable languages, Some properties of recursive and recursively enumerable languages, Codes for TMs. A language that is not recursively enumerable (the diagonalization language). The universal language, Undecidability of the universal language, The Halting problem, Undecidable problems about TMs.

Module 13
(2 Lectures)

Post's Correspondence Problem (PCP) -Definition, Undecidability of PCP.

Other undecidability problems e.g. some problems related to CFLs

Module 14
(2 Lectures)

Context sensitive language and linear bounded automata. Chomsky hierarchy

Download Syllabus (PDF)

 

 

 

 

 

Top of this page

Other Departments: Core Sciences      Computer Science and Engineering    Electrical Engineering  
 Electronics and Communication Engineering
   Mechanical Engineering   Civil Engineering

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


Site Maintained by Web Studio IIT Madras. Contact Webmaster:
mangal@iitm.ac.in