Theory of Computation (MCA132) crash course, Online MCA, Semester 1:
This subject covers finite automata, formal languages and the Chomsky hierarchy, regular expressions and grammars, context-free grammars with pushdown…
- 17 video lessons
- 2h 58m
- Study notes
- 85 quiz questions
- Assignment
17 lessons in Theory of Computation
Each lesson pairs one topic with a hand-picked video, trimmed to the part that teaches it.
About this subject
This subject covers finite automata, formal languages and the Chomsky hierarchy, regular expressions and grammars, context-free grammars with pushdown automata, and Turing machines with linear bounded automata. After it you will be able to design and minimize automata, convert between automata, grammars and regular expressions, prove languages non-regular or non-context-free with pumping lemmas, and reason about decidability, the halting problem and NP-completeness.
- 1
Introduction to Finite Automata
Module I, : Definition of an Automaton, Description of a Finite Automation, Transition Systems, Properties of Transition Functions, Acceptability of a String by a Finite Automation
Introduction to Finite Automata· Neso Academy· 13 min
Study notes 5 quiz questionsWatch lesson - 2
NFA and DFA Equivalence
Module I, : Nondeterministic Finite State Machines, The Equivalence of DFA and NDFA
Lec-17: What is NFA in TOC in Hindi | Non Deterministic Finite Automata· Gate Smashers· 9 min
Study notes 5 quiz questionsWatch lesson - 3
Mealy and Moore Machines
Module I, : Mealy and Moore Models
Finite Automata With Outputs· Neso Academy· 11 min
Study notes 5 quiz questionsWatch lesson - 4
DFA Minimization
Module I, : Minimization of Finite Automata Exercises
Minimization of DFA (Example 1)· Neso Academy· 16 min
Study notes 5 quiz questionsWatch lesson - 5
Formal Languages and Chomsky Hierarchy
Module II, : Basic Definitions and Examples, Chomsky Classification of Languages, Languages and Their Relation
Chomsky hierarchy of languages || Types of languages || TOC || FLAT || Theory of Computation· Sudhakar Atchala· 8 min
Study notes 5 quiz questionsWatch lesson - 6
Recursive and Recursively Enumerable Languages
Module II, : Recursive and Recursively Enumerable Sets, Operations on Languages, Languages and Automata
Lec-64: Recursive vs Recursive Enumerable Languages | TOC· Gate Smashers· 7 min
Study notes 5 quiz questionsWatch lesson - 7
Regular Expressions and Finite Automata
Module III, : Regular Expressions, Finite Automata and Regular Expressions
Lec-29: Regular Expressions in TOC with examples | Formal Definition· Gate Smashers· 10 min
Study notes 5 quiz questionsWatch lesson - 8
Pumping Lemma for Regular Languages
Module III, : Pumping Lemma for Regular Sets, Application of Pumping lemma
Lec-33: Pumping lemma for regular languages in TOC with examples· Gate Smashers· 12 min
Study notes 5 quiz questionsWatch lesson - 9
Closure Properties and Regular Grammars
Module III, : Closure Properties of Regular Sets, Regular Sets and Regular Grammars
Lec-34: Closure properties of regular languages in TOC· Gate Smashers· 10 min
Study notes 5 quiz questionsWatch lesson - 10
Context-Free Grammars, Derivation Trees and Ambiguity
Module IV, : Context-free languages and Derivation Trees, Ambiguity in Context free Grammars
Derivation Tree (Left & Right Derivation Trees)· Neso Academy· 13 min
Study notes 5 quiz questionsWatch lesson - 11
CFG Simplification and Normal Forms (CNF, GNF)
Module IV, : Simplification of Context-free Grammars, Normal Forms
Chomsky Normal Form & CFG to CNF Conversion· Neso Academy· 7 min
Study notes 5 quiz questionsWatch lesson - 12
Pumping Lemma for Context-Free Languages
Module IV, : Pumping Lemma and Decision Algorithms for context free languages
Pumping Lemma (For Context Free Languages)· Neso Academy· 8 min
Study notes 5 quiz questionsWatch lesson - 13
Pushdown Automata
Module IV, : Basic Definitions of Pushdown Automata, Acceptance by pda, Pushdown Automata and Context free Languages, Parsing and Pushdown Automata
9.2 Pushdown Automata PDA | Pushdown Automata explained in Detail | Theory of Computation | TOC· KnowledgeGATE by Sanchit Sir· 19 min
Study notes 5 quiz questionsWatch lesson - 14
Turing Machine Basics
Module IV, : Turing Machine Model, Representation of Turing Machines, Language Acceptability by Turing Machines
Introduction to Turing Machine || Formal Definition || Model || FLAT || TOC || Theory of Computation· Sudhakar Atchala· 9 min
Study notes 5 quiz questionsWatch lesson - 15
Designing Turing Machines and Universal TM
Module IV, : Design of Turing Machines, Universal Turing Machines and Other modifications, Turing Machines and Type 0 Grammars
Lec-60: Turing Machine for a^nb^n | Design Turing Machine· Gate Smashers· 12 min
Study notes 5 quiz questionsWatch lesson - 16
Linear Bounded Automata
Module IV, : The Model of Linear Bounded Automaton, Linear Bounded Automata and languages
Linear Bounded Automata || TOC || FLAT || Theory of Computation· Sudhakar Atchala· 7 min
Study notes 5 quiz questionsWatch lesson - 17
Halting Problem and NP-Completeness
Module IV, : Halting Problem of Turing Machines, NP-Completeness
The Halting Problem· Neso Academy· 7 min
Study notes 5 quiz questionsWatch lesson
Assignment
Theory of Computation Problem Set: From Automata to Undecidability
Less scrolling. More passing.
- Free
Hand-picked video lessons
17 short lessons, each with the best YouTube explanation we could find, trimmed to the part that matters.
- Free login
Study notes
17 lessons come with a summary, key points, key terms and takeaways for quick revision.
- Free login
Quizzes
85 questions across the course, with the right answer and why, the moment you pick.
- Free login
Assignments
1 subject assignments with clear tasks, so you practise what each subject actually asks of you.
- Free login
Notebook
Write notes beside the video, stamped with the exact time, and jump back to that moment later.
- Free login
Progress that follows you
Completed lessons, quiz scores and where you stopped, saved to your account on every device.
- Live chat pass
Live chat
A members-only live chat beside every lesson: doubts, tips, stickers and GIFs with your batch. One ₹19 pass opens every live chat.
The Online MCA live chat. Study together, live.
A live chat right beside the video, shared by everyone studying Online MCA. Ask a Theory of Computation doubt mid-lesson, share a shortcut, celebrate a finished semester.
- Live chat beside every lesson
- One live chat for all of Online MCA
- Members-only stickers & GIFs
- One ₹19 pass opens every live chat
Online MCA live chat
Anyone else finding Theory of Computation tricky? 😅
Lesson 2 cleared it up for me. Watch it before the quiz
Doing it now, thanks!
Starting Advanced Database Management System tonight if anyone wants to go together
More from Online MCA Semester 1
All subjects- Sem 1
MCA103
Advanced Database Management System
This subject covers PL/SQL programming (blocks, cursors, exceptions, triggers, procedures and packages) along with distributed, parallel and object-oriented…
- 18 lessons
- 5h 37m
- Notes
- Quiz
- Sem 1
MCA133
Analysis and Design of Algorithms
This subject covers how to measure the time and space complexity of algorithms and the main design techniques: divide and conquer, dynamic programming, greedy…
- 18 lessons
- 6h 17m
- Notes
- Quiz
- Sem 1
MCA134
Computer Graphics
This subject covers the fundamentals of computer graphics: display and input hardware, algorithms for drawing lines, circles, ellipses and filled areas, 2D and…
- 14 lessons
- 4h 12m
- Notes
- Quiz
- Sem 1
MCA102
Core Java
This subject covers core Java programming, from the JVM, data types and control flow through classes, inheritance, interfaces, packages, exception handling and…
- 15 lessons
- 9h 58m
- Notes
- Quiz
- Sem 1
MCA135
Data Warehousing and Mining
This subject covers how data warehouses are designed, built and tuned for multidimensional analysis, and how data mining techniques such as clustering,…
- 19 lessons
- 3h 58m
- Notes
- Quiz
- Sem 1
MCA131
Mobile Computing
This subject covers how mobile and wireless networks work, from GSM architecture and wireless medium access to Mobile IP, mobile TCP variants, wireless LANs,…
- 15 lessons
- 2h 20m
- Notes
- Quiz
Theory of Computation: common questions
This subject covers finite automata, formal languages and the Chomsky hierarchy, regular expressions and grammars, context-free grammars with pushdown automata, and Turing machines with linear bounded automata. After it you will be able to design and minimize automata, convert between automata, grammars and regular expressions, prove languages non-regular or non-context-free with pumping lemmas, and reason about decidability, the halting problem and NP-completeness. It's the Theory of Computation subject of Online MCA, Semester 1, in 17 lessons: Introduction to Finite Automata; NFA and DFA Equivalence; Mealy and Moore Machines; DFA Minimization; Formal Languages and Chomsky Hierarchy; Recursive and Recursively Enumerable Languages; Regular Expressions and Finite Automata; Pumping Lemma for Regular Languages; Closure Properties and Regular Grammars; Context-Free Grammars, Derivation Trees and Ambiguity; CFG Simplification and Normal Forms (CNF, GNF); Pumping Lemma for Context-Free Languages; Pushdown Automata; Turing Machine Basics; Designing Turing Machines and Universal TM; Linear Bounded Automata; Halting Problem and NP-Completeness.
Yes. Every video lesson is free to watch without an account. A free login unlocks study notes, quizzes, the assignment, a notebook and progress that syncs across devices.
About 2h 58m of video across 17 lessons, plus time for notes and quizzes. Go at your own pace; your place is saved.
Yes: “Theory of Computation Problem Set: From Automata to Undecidability”. It comes after the last lesson, with a brief, clear tasks and how the work is judged.
A members-only live chat beside the video, shared by everyone studying Online MCA, where learners ask doubts, share tips and react with stickers and GIFs. One ₹19 pass, paid once from your InsideEdge wallet, opens the live chat for every degree.
No. It's a crash course to help you understand and revise the subject quickly. Use it alongside your official study material and assignments.