Description: Computer Science – Theory of Computation
Curriculum
- 1 Section
- 42 Lessons
- 10 Weeks
Expand all sectionsCollapse all sections
- Computer Science - Theory of Computation42
- 2.1What is theory of computation?
- 2.2Introduction to finite automaton.
- 2.3Finite automata continued, deterministic finite automata(DFAs),
- 2.4Regular languages, their closure properties.
- 2.5DFAs solve set membership problems in linear time, pumping lemma.
- 2.6More examples of nonregular languages, proof of pumping lemma
- 2.7A generalization of pumping lemma, nondeterministic finite automata (NFAs)
- 2.8Formal description of NFA, language accepted by NFA, such languages are also regular.
- 2.9Guess and verify-paradigm for nondeterminism.
- 2.10NFAs with epsilon transitions.
- 2.11Construction of a regular expression for a language given a DFA accepting it.
- 2.12Closure properties continued.
- 2.13Closure under reversal, use of closure properties.
- 2.14Decision problems for regular languages.
- 2.15About minimization of states of DFAs. Myhill-Nerode theorem.
- 2.16Continuation of proof of Myhill-Nerode theorem.
- 2.17Application of Myhill-Nerode theorem. DFA minimization.
- 2.18DFA minimization continued.
- 2.19Introduction to context free languages (cfls)
- 2.20Languages generated by a cfg, leftmost derivation, more examples of cfgs and cfls.
- 2.21Parse trees, inductive proof that L is L(G). All regular languages are context free.
- 2.22Towards Chomsky normal forms: elimination of useless symbols
- 2.23Simplification of cfgs continued, Removal of epsilon productions
- 2.24Elimination of unit productions. Converting a cfg into Chomsky normal form.
- 2.25Pumping lemma for cfls. Adversarial paradigm.
- 2.26Completion of pumping lemma proof
- 2.27Closure properties continued. cfls not closed under complementation.
- 2.28Another example of a cfl whose complement is not a cfl. Decision problems for cfls.
- 2.29More decision problems. CYK algorithm for membership decision.
- 2.30Introduction to pushdown automata (pda).
- 2.31pda configurations, acceptance notions for pdas. Transition diagrams for pdas
- 2.32Equivalence of acceptance by empty stack and acceptance by final state.
- 2.33Turing machines (TM): motivation, informal definition, example, transition diagram.
- 2.34Execution trace, another example (unary to binary conversion).
- 2.35Example continued. Finiteness of TM description
- 2.36Notion of non-acce`ptance or rejection of a string by a TM. Multitrack TM
- 2.37Simulation of multitape TMs by basic model. Nondeterministic TM (NDTM).
- 2.38Counter machines and their equivalence to basic TM model.
- 2.39TMs can simulate computers, diagonalization proof.
- 2.40Existence of non-r.e. languages, recursive languages, notion of decidability.
- 2.41Separation of recursive and r.e. classes, halting problem and its undecidability.
- 2.42
