Theory of Computation II

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

Beginner 0(0 Ratings) 0 Students enrolled English
Created by skill expert
Last updated Fri, 17-Jun-2022
+ View more
Course overview

 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

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

skill expert

0 Reviews | 17 Students | 467 Courses
Student feedback
0
0 Reviews
  • (0)
  • (0)
  • (0)
  • (0)
  • (0)

Reviews

Free
Includes: