IIT Madras Course , Prof. Kamala Krithivasan

**595**students enrolled

IIT Madras Course , Prof. Kamala Krithivasan

The objective of the course is to provide an exposition first to the notion of computability, then to the notion of computational feasibility or tractability. We first convince ourselves that for our purpose it suffices to consider only language recognition problems instead of general computational problems. We then provide a thorough account of finite state automata and regular languages, not only because these capture the simplest language class of interest and are useful in many diverse domains. But also because many fundamental notions like nondeterminism, proofs of impossibility, etc. get discussed at a conceptually very simple level. We then consider context grammars and languages, and their properties. Next, we consider Turing machines (TMs), show that as a model it is very robust, and the reasonableness of the Church-Turing hypothesis. After we realize TMs can work with (codes of) TMs as inputs, we obtain a universal TM. We then obtain the separation of the classes r.e., and recursive. A number of TM related problems are shown to be undecidable. Next,Posts correspondence problem (PCP) is shown undecidable. Finally, we introduce the notion of feasible or tractable computation. Classes NP, co-NP are defined and we discuss why these are important. We discuss the extended Church-Turing hypothesis. After we discuss polynomial time many-one reducibility and prove Cook-Levin theorem, a number of natural problems from different domains are shown NP-complete. The treatment is informal but rigorous. Emphasis is on appreciating that the naturalness and the connectedness of all the different notions and the results that we see in the course. Contents: Regular languages Introduction: Scope of study as limits to compubality and tractability. Why it suffices to consider only decision problems, equivalently, set membership problems. Notion of a formal language. DFAs and notion for their acceptance, informal and then formal definitions. Class of regular languages. Closure of the class under complementation, union and intersection. Strategy for designing DFAs. Pumping lemma for regular languages. Its use as an adversarial game. Generalized version. Converses of lemmas do not hold. NFAs. Notion of computation trees. Definition of languages accepted. Construction of equivalent DFAs of NFAs. NFAs with epsilon transitions. Guess and check paradigm for design of NFAs. Regular expressions. Proof that they capture precisely class of regular languages. Closure properties of and decision problems for regular languages. Myhill-Nerode theorem as characterization of regular languages.States minimization of DFAs. Context free languages: Notion of grammars and languages generated by grammars. Equivalence of regular grammars and finite automata. Context free grammars and their parse trees. Context free languages. Ambiguity. Pushdown automata (PDAs): deterministic and nondeterministic. Instantaneous descriptions of PDAs.Language acceptance by final states and by empty stack. Equivalence of these two. PDAs and CFGs capture precisely the same language class. Elimination of useless symbols, epsilon productions, unit productions from CFGs. Chomsky normal form. Pumping lemma for CFLs and its use. Closure properties of CFLs. Decision problems for CFLs. Turing machines, r.e. languages, undecidability: Informal proofs that some computational problems cannot be solved. Turing machines (TMs), their instantaneous descriptions. Language acceptance by TMs. Hennie convention for TM transition diagrams.Robustness of the model-- equivalence of natural generalizations as well as restrictions equivalent to basic model. Church-Turing hypothesis and its foundational implications. Codes for TMs. Recursively enumerable (r.e.) and recursive languages. Existence of non-r.e. languages. Notion of undecidable problems. Universal language and universal TM. Separation of recursive and r.e. classes. Notion of reduction. Some undecidable problems of TMs. Rices theorem. Undecidability of Posts correspondence problem (PCP), some simple applications of undecidability of PCP. Intractability: Notion of tractability/feasibility. The classes NP and co-NP, their importance. Polynomial time many-one reduction. Completeness under this reduction. Cook-Levin theorem: NP-completeness of propositional satisfiability, other variants of satisfiability. NP-complete problems from other domains: graphs (clique, vertex cover, independent sets, Hamiltonian cycle), number problem (partition), set cover.

Up Next

You can skip ad in

SKIP AD >

Advertisement

- 2x
- 1.5x
- 1x
- 0.5x
- 0.25x

EMBED LINK

COPY

DIRECT LINK

COPY

PRIVATE CONTENT

OK

Enter password to view

Please enter valid password!

- Play Pause
- Mute UnMute
- Fullscreen Normal
- @Your Company Title

0:00

4.1 (91 Ratings)

Theory of Computation by Prof.Kamala Krithivasan,Department of Computer Science and Engineering,IIT Madras. For more details on NPTEL visit httpnptel.iitm.ac.in

Heads up!

IITMadras delivers the above video lessons under NPTEL program, there are more than 6000+ nptel video lectures by other IITs as well.
69%

7%

4%

3%

16%

- 1.GRAMMARS AND NATURAL LANGUAGE PROCESSING
- 2.GRAMMARS AND LANGUAGES GENERATED
- 3.GRAMMARS AND LANGUAGES GENERATED (Contd)
- 4.AMBIGUITY IN CFG
- 5.SIMPLICATION OF CFG
- 6.REMOVAL OF UNIT PRODUCTIONS , CHOMSKY NORMAL FORM FOR CFG
- 7.GREIBACH NORMAL FORM FOR CFG
- 8.FINAL STATE AUTOMATA
- 9.NON-DETERMINISTIC FSA
- 10.NON DETERMINISTIC FSA (Contd)
- 11.NON DETERMINISTIC FSA WITH E(Epsilon)- MOVES
- 12.EQUIVALENCE BETWEEN FSA AND TYPE 3 GRAMMARS
- 13.REGULAR EXPRESSIONS , REGULAR EXPRESSIONS TO NFSA
- 14.DFSA TO REGULAR EXPRESSIONS
- 15.PROBLEMS AND SOLUTIONS
- 16.PUMPING LEMMAS FOR REGULAR SETS AND CFL
- 17.MYHILL-NERODE THEOREM
- 18.MINIMIZATION OF DFSA
- 19.FSA WITH OUTPUT MOORE AND MEALY MACHINES
- 20.PUSHDOWN AUTOMATA
- 21.PUSHDOWN AUTOMATA,EQUIVALENCE BETWEEN ACCEPTANCE BY EMPTY STORE
- 22.PUSHDOWN AUTOMATA CFG TO PDA
- 23.PUSHDOWN AUTOMATA PDA TO CFG
- 24.PROBLEMS AND SOLUTIONS-I
- 25.PROBLEMS AND SOLUTIONS - III
- 26.TURING MACHINES
- 27.TURING MACHINES (Contd)
- 28.TURING MACHINE AS ACCEPTOR , TECHNIQUES FOR TM CONSTRUCTION
- 29.GENERALIZED VERSIONS OF TURING MACHINES
- 30.TURING MACHINE AS A GENERATING DEVICE
- 31.RECURSIVE SETS , RECURSIVELY INNUMERABLE SETS , ENCODING OF TM , HALTING PROBLEM
- 32.RICES THEOREM,LINEAR BOUNDED AUTOMATA,PROPERTIES OF TM
- 33.PROBLEMS AND INSTANCES , UNIVERSAL TM , DECIDABILITY
- 34.DNA COMPUTING
- 35.GRAMMAR SYSTEMS
- 36.L - SYSTEMS
- 37.POSTS CORRESPONDENCE PROBLEMS (Contd) TIME AND TAPE COMPLEXITY OT TM
- 38.NP - COMPLETE PROBLEMS , COOKS THEOREM
- 39.POSTS CORRESPONDENCE PROBLEMS
- 40.REGULATED REWRITING
- 41.MEMBRANE COMPUTING
- 42.NP - COMPLETE PROBLEMS (Contd)

- FreeVideoLectures aim to help millions of students across the world acquire knowledge, gain good grades, get jobs, assist in getting promotions through quality learning material.

- You can write to us
- help@freevideolectures.com

2018 FreeVideoLectures. All rights reserved. FreeVideoLectures only promotes free course material from different sources, we are not endrosed by any university.