Class Central is learner-supported. When you buy through links on our site, we may earn an affiliate commission.

# Theory of Computation

### Overview

Explore a comprehensive 10-hour lecture series on Theory of Computation (TOC), covering essential topics for GATE and UGC NTA NET exams. Delve into fundamental concepts such as languages, automata, grammars, and their relationships. Learn about Deterministic and Non-deterministic Finite Automata (DFA/NFA), regular expressions, and closure properties. Study advanced topics including Moore and Mealy machines, pumping lemma, context-free languages, pushdown automata, and Turing machines. Master key algorithms like CYK and understand normal forms in context-free grammars. Gain practical skills in designing automata, converting between different types, and solving complex problems in computational theory.

### Syllabus

Lec-1:Syllabus of TOC(Theory of Computation) for GATE | UGC NTA NET| Imp Points.
Lec-2:Introduction to TOC | What is Language in TOC with Examples in Hindi.
Lec-3:What is Automata in TOC | Theory of Computation.
Lec-4:Power of Sigma Î£ in TOC | Kleene closure in TOC.
Lec-5: What is Grammar in TOC | Must Watch.
Lec-6: What is DFA in TOC with examples in hindi.
Lec-7: DFA Example 1 | How to Construct DFA in TOC.
Lec-8: DFA Example 2 | DFA of language with all strings end with 'a'.
Lec-9: DFA Example 3 | DFA of language with all strings starting with 'a' and ending with 'b'.
Lec-10:DFA of language with all strings Not starting with 'a' OR Not ending with 'b' | DFA Example 4.
Lec-11:DFA of all strings in which 2nd symbol is '0' and 4th symbol is '1'| DFA Example 6.
Lec-12: DFA of all binary strings divisible by 3 | DFA Example 5.
Lec-13: What is NFA in TOC in Hindi | Non Deterministic Finite Automata.
Lec-14: DFA vs NFA in TOC in Hindi with examples | Must Watch.
Lec-15: Design NFA of all binary strings in which 2nd last bit is 1 | NFA Designing | TOC in Hindi.
Lec-16: Convert NFA to DFA with example in Hindi | How to Convert NFA to DFA.
Lec-17: DFA for Even a and Even b | Even a Odd b | Odd a and Even b | Odd a Odd b | TOC.
Lec-18: Eliminate Epsilon Îµ-moves | Conversion from epsilon nfa to nfa.
Lec-19: Limitations of DFA and Applications of DFA in TOC in Hindi.
Lec-20: Moore Machine in TOC with example | What is Moore Machine in Hindi.
Lec-21: Mealy Machine in TOC | Formal Definition | Mealy Machine in Hindi.
Lec-22: Difference between Mealy and Moore Machine in Hindi | All imp points.
Lec-23: Moore to Mealy Conversion with example in Hindi | TOC.
Lec-24: Mealy to Moore Conversion with Example in Hindi.
Lec-25: Epsilon NFA in hindi | Îµ-NFA Formal Definition.
Lec-26: Minimization of DFA in Hindi with example | TOC.
Lec-27: Regular Expressions in TOC with examples | Formal Definition.
Lec-28: Regular Expressions for Finite Languages Example 1 | TOC.
Lec-29: Regular Expressions for Infinite Languages Example 2 | TOC.
Lec-30: Imp. Question on Regular Expressions for all Competitive Exams | TOC.
Lec-31: Pumping lemma for regular languages in TOC with examples.
Lec-32: Closure properties of regular languages in TOC.
Lec-33: Reversal Operation in toc | How regular languages closured under reversal.
Lec-34: Quotient operation in toc with example | Closure Properties.
Lec-35: INIT Operation in TOC.
Lec-36: Regular languages Not Closed under Infinite Union | TOC.
Lec-37: Closure Properties Of Various Languages in TOC | Theory Of Computation.
Lec-38: Languages, Automata, Grammars in TOC | Comparison between them.
Lec-39: Question on DCFL and CFL in toc.
Lec-40: Imp Question on Decidability and closure property | TOC.
Lec-41: TOC Most Imp 10 Questions for Every Exam | TOP 10 Imp questions of Theory of Computation.
Lec-42: TOC Most Imp 10 Questions with explanation | 10 Questions for every exam.
Lec-43: Homomorphism in Regular Languages | closure Properties | TOC.
Lec-44: Inverse Homomorphism in Regular Languages | Closure Properties in TOC.
Lec-45: Decidability & Undecidability table in toc for all languages.
Lec-46: CFL and CFG Introduction and Syllabus discussion.
Lec-47: What is Context free grammar in TOC | Formal Definition.
Lec-48: Convert Context free language to Context free grammar with examples | TOC.
Lec-49: Left Most & Right Most Derivation in CFG | TOC.
Lec-50: What is Pushdown Automata in TOC | Definition & Explanation in Hindi.
Lec-51: Design PDA for 0^n1^2n CFL Language | Very Imp | Must Watch.
Lec-52: Design PDA for {w | na(w) = nb(w)} CFL language | Pushdown automata | TOC.
Lec-53: Closure Properties of CFL (Context Free Languages) with explanation in Hindi.
Lec-54: Remove Null Production from CFG (Context Free Grammar) with example in Hindi.
Lec-55: Remove Unit Production from CFG(Context Free Grammar) in Hindi.
Lec-56: Introduction to Turing Machine and its Definition in Hindi | TOC.
What is LBA(Linear Bounded Automata) | All Points Covered | First Video#2021.
Turing Machine for a^nb^n | Design Turing Machine.
Turing Machine for a^nb^nc^n | Design Turing Machine.
Recursive vs Recursive Enumerable Languages | TOC.
Turing Machine for 1's Complement | Transition Table & Diagram.
Modifications in Turing machine.
CYK Algorithm | Membership Algorithm in CFG | TOC.
CNF Vs GNF | Chomsky vs Greibach Normal Form | CFG in TOC.

Gate Smashers

## Reviews

Start your review of Theory of Computation

### Never Stop Learning.

Get personalized course recommendations, track subjects and courses with reminders, and more.