IIT Kanpur Course , Prof. Somenath Biswas

**146**students enrolled

IIT Kanpur Course , Prof. Somenath Biswas

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. Rice's theorem - Undecidability of Post's 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

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. Rice's theorem - Undecidability of Post's 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

5.0 (3 Ratings)

Theory of Computation by Prof. Somenath Biswas,Computer Science and Engineering, IIT Kanpur.For more details on NPTEL visit httpnptel.ac.in

100%

- 1.What is theory of computation?
- 2.Introduction to finite automaton.
- 3.Finite automata continued, deterministic finite automata(DFAs),
- 4.Regular languages, their closure properties.
- 5.DFAs solve set membership problems in linear time, pumping lemma.
- 6.More examples of nonregular languages, proof of pumping lemma
- 7.A generalization of pumping lemma, nondeterministic finite automata (NFAs)
- 8.Formal description of NFA, language accepted by NFA, such languages are also regular.
- 9.Guess and verify paradigm for nondeterminism.
- 10.Mod- 01 Lec-10 NFAs with epsilon transitions.
- 11.Regular expressions, they denote regular languages.
- 12.Construction of a regular expression for a language given a DFA accepting it.
- 13.Closure properties continued.
- 14.Closure under reversal, use of closure properties.
- 15.Decision problems for regular languages.
- 16.About minimization of states of DFAs. Myhill-Nerode theorem.
- 17.Continuation of proof of Myhill-Nerode theorem.
- 18.Application of Myhill-Nerode theorem. DFA minimization.
- 19.DFA minimization continued.
- 20.Introduction to context free languages (cfls)
- 21.Languages generated by a cfg, leftmost derivation, more examples of cfgs and cfls.
- 22.Parse trees, inductive proof that L is L(G). All regular languages are context free.
- 23.Towards Chomsky normal forms elimination of useless symbols
- 24.Simplification of cfgs continued, Removal of epsilon productions
- 25.Elimination of unit productions. Converting a cfg into Chomsky normal form.
- 26.Pumping lemma for cfls. Adversarial paradigm.
- 27.Completion of pumping lemma proof
- 28.Closure properties continued. cfls not closed under complementation.
- 29.Another example of a cfl whose complement is not a cfl. Decision problems for cfls.
- 30.More decision problems. CYK algorithm for membership decision.
- 31.Introduction to pushdown automata (pda).
- 32.pda configurations, acceptance notions for pdas. Transition diagrams for pdas
- 33.Equivalence of acceptance by empty stack and acceptance by final state.
- 34.Turing machines (TM) motivation, informal definition, example, transition diagram.
- 35.Execution trace, another example (unary to binary conversion).
- 36.Example continued. Finiteness of TM description
- 37.Notion of non-acceptance or rejection of a string by a TM. Multitrack TM
- 38.Simulation of multitape TMs by basic model. Nondeterministic TM (NDTM).
- 39.Counter machines and their equivalence to basic TM model.
- 40.TMs can simulate computers, diagonalization proof.
- 41.Existence of non-r.e. languages, recursive languages, notion of decidability.
- 42.Separation of recursive and r.e. classes, halting problem and its undecidability.

- 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.