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

Other Resources

Course Curriculum

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

Course Reviews


  • 5 stars0
  • 4 stars0
  • 3 stars0
  • 2 stars0
  • 1 stars0

No Reviews found for this course.


FreeVideoLectures Provides you complete information about best courses online, Video tutorials, helps you in building a career !!

Learn More About us All rights reserved.

Setup Menus in Admin Panel