Learning objectives :

Course should provide a formal connection between algorithmic problem solving and the theory of languages and automata and develop them into a mathematical (and less magical) view towards algorithmic design and in general computation itself. The course should in addition clarify the practical view towards the applications of these ideas in the engineering part of CS.

Syllabus

Four basic themes (but related in a flow) :

Finite Automata & Regular Languages

Languages vs Problems. Finite State Automata, Regular Languages. Closure properties, Limitations, Pumping Lemma, Myhill-Nerode relations, Quotient Construction. Minimization Algorithm.

Non-determinism & Regular Expressions

Notion of non-determinism. Acceptance condition. Subset construction. Pattern matching and regular expressions. Regular Expressions and Regular languages. More closure properties of regular languages.

Grammars & Context-free Languages(CFLs)

Grammars and Chomsky Hierarchy, CFLs, Regular Grammars, Chomsky Normal Form, Pumping Lemma for CFLs, Inherent Ambiguity of Context-Free Languages, Cock-Younger-Kasami Algorithm, Applications to Parsing. Pushdown Automata(PDA), PDA vs CFLs. Deterministic CFLs.

Turing Machines & Computability

Introduction to Turing Machines, Configurations, Halting vs Looping. Multi-tape Turing machines. Recursive and Recursively enumerable languages. Undecidability of Halting Problem. Reductions. Introduction to Theory of NP-completeness.

TextBook(s)

  1. Automata and Computability, Dexter C. Kozen, Springer Publishers, 2007.

  2. Introduction to Automata Theory, Languages and Computation, Hopcroft, Motwani, and Ullman, Pearson Publishers, Third Edition, 2006.

References

  1. Elements of the Theory of Computation, H. R. Lewis and C.H. Papadimitriou, Prentice Hall Publishers, 1981

  2. Introduction to Languages and the Theory of Computation, John. C. Martin, Tata McGraw-Hill, 2003.

Meta Data

  • Proposing Faculty : IIT Madras course
  • Department / Centre : Computer Science and Engineering
  • Programme : B.Tech
  • Proposal Type: Old
  • Offerings
    • 2017 Jan-Apr Dr. Deepak Rajendraprasad

Past Offerings

  • Offered in Jan-May, 2018 by Deepak
  • Offered in Jan-May, 2017 by Deepak

Course Metadata

Item Details
Course Title Languages, Machines and Computation
Course Code CS2200
Course Credits 3-1-0-4
Course Category PMT
Approved on Senate of IIT Palakkad