EE-Learning
Decision problems for regular languages.
Catogry:
Computing
Subject:
Computer Science
Course:
Theory Of Computation II
Lecture List
Separation of recursive and r.e. classes, halting problem and its undecidability.
Existence of non-r.e. languages, recursive languages, notion of decidability.
TMs can simulate computers, diagonalization proof.
Counter machines and their equivalence to basic TM model.
Simulation of multitape TMs by basic model. Nondeterministic TM (NDTM).
Notion of non-acceptance or rejection of a string by a TM. Multitrack TM
Example continued. Finiteness of TM description
Execution trace, another example (unary to binary conversion).
Turing machines (TM): motivation, informal definition, example, transition diagram.
Equivalence of acceptance by empty stack and acceptance by final state.
pda configurations, acceptance notions for pdas. Transition diagrams for pdas
Introduction to pushdown automata (pda).
More decision problems. CYK algorithm for membership decision.
Another example of a cfl whose complement is not a cfl. Decision problems for cfls.
Closure properties continued. cfls not closed under complementation.
Completion of pumping lemma proof
Pumping lemma for cfls. Adversarial paradigm.
Elimination of unit productions. Converting a cfg into Chomsky normal form.
Simplification of cfgs continued, Removal of epsilon productions
Towards Chomsky normal forms: elimination of useless symbols
Parse trees, inductive proof that L is L(G). All regular languages are context free.
Languages generated by a cfg, leftmost derivation, more examples of cfgs and cfls.
Introduction to context free languages (cfls)
DFA minimization continued.
Application of Myhill-Nerode theorem. DFA minimization.
Continuation of proof of Myhill-Nerode theorem.
About minimization of states of DFAs. Myhill-Nerode theorem.
Decision problems for regular languages.
Closure under reversal, use of closure properties.
Closure properties continued.
Construction of a regular expression for a language given a DFA accepting it.
Regular expressions, they denote regular languages.
Mod- 01 Lec-10 NFA’s with epsilon transitions.
‘Guess and verify’ paradigm for nondeterminism.
Formal description of NFA, language accepted by NFA, such languages are also regular.
A generalization of pumping lemma, nondeterministic finite automata (NFAs)
More examples of nonregular languages, proof of pumping lemma
DFAs solve set membership problems in linear time, pumping lemma.
Regular languages, their closure properties.
Finite automata continued, deterministic finite automata(DFAs),
Introduction to finite automaton.
What is theory of computation?