Lecture 12 of 39Week 3
Non-regular languages and pumping lemma
Prof. Raghunath Tewari · IIT Kanpur
Credits and licence
- From
- Theory of Computation, IIT Kanpur (at NPTEL)
- Licence
- CC BY-NC-SA, as NPTEL states it. Non-commercial use only.
- Attribution
- NPTEL states: "Distributed under Creative Commons Attribution-ShareAlike / CC BY - NC - SA", beside a BY-NC-SA badge.
- Who can watch
- Tweens profiles and older. How courses are placed
All the lectures
- Introduction to Finite Automata
- Basic Notation and Convention, DFA
- Example of DFAs
- Computation by DFA and Regular operation
- Introduction to Nondeterminism
- NFA, definition and examples
- Equivalence of NFA and DFA, Closure properties
- Regular expressions
- Algebraic properties, RE to NFA conversion
- GNFA to RE conversion
- More closure properties of regular languages
- Non-regular languages and pumping lemma
- Examples of non-regular languages
- DFA minimization
- Introduction to CFGs
- Examples of CFGs, Reg subset of CFL
- Parse tree, derivation, ambiguity
- Normal forms, Chomsky normal form
- Non-CFLs, pumping lemma
- Examples of non- CFLs
- Pushdown Automata
- Pushdown Automata - Definition and Example
- Pushdown Automata - Examples and Relation with CFGs
- Closure Properties of CFLs
- Deterministic Context Free Languages
- Turing Machine
- More on Turing Machine
- Non deterministic Turing Machine
- Configuration Graphs
- Decidability properties of Regular and Context Free Languages
- Undecidability
- More on Undecidability
- Reduction
- Applications of Reduction
- Rice's theorem
- Introduction to Computational Complexity Theory
- More on the class NP
- NP-Completeness
- More on NP-Completeness