Theory of Computation

Name: Theory of Computation
Rating: 4.3 (67 reviews)

Machines and Models

Created byDr Amol Prakash Bhagat

Last updated 11/2023

English

What you'll learn

Construction of finite state machines to solve problems in computing
Regular expressions for the formal languages
Construct and analyze Push Down, Turing Machine, Linear Bounded Automata for formal languages
Understanding of the Chomsky Hierarchy
Decidability and un-decidability problems

Course content

6 sections • 73 lectures • 30h 19m total length

Introduction22:40
Introduction
Applications of Theory of Computation
Syntax Errors
High level language statements
Types of machines
Theory of Computation, Alphabets, Strings, Languages22:34
Theory of Computation
Alphabets
Strings
Languages
Operations27:32
Operations
Length of String
Reverse of String
Prefix
Suffix
Palindrome
Concatenation
Transpose
Finite Automaton28:39
Finite Automaton
Finite State Machine
Finite Automata
Finite Automaton with a Finite Memory
Finite Automaton without Memory
Moore Machine
Mealy Machine
A 4 bit shift register as finite state machine22:20
A 4 bit shift register as finite state machine
4-bits shift register finite automaton model
Input, output, states, state relation, output relation
Transition table.
Block Diagram of a Finite Automaton12:55
Block Diagram of a Finite Automaton
Input Tape, Read Head, Finite Control
Description of Finite Automaton21:11
Description of Finite Automaton
5 - tuples
Finite Automaton without Output
Direct Transition Function
Indirect Transition Function
Mapping Function
Transition Table
Transition Diagram
String Processing by Finite Automaton21:27
String Processing by Finite Automaton
Acceptability of String by Finite Automata
Verification of String Acceptability on given Finite Automaton
Language of a Finite Automaton14:06
Language of a Finite Automaton
Identifying Language of a Finite Automaton
Examples - String Acceptability and Language of a Finite Automaton15:50
Examples - String Acceptability
Language of a Finite Automaton
Deterministic and Nondeterministic Finite Automata, DFA, NFA, NDFA27:57
Deterministic and Nondeterministic Finite Automata
DFA, NFA, NDFA
Acceptance of String by Nondeterministic Finite Automata, NFA, NDFA24:10
Acceptance of String by Nondeterministic Finite Automata, NFA, NDFA
Converting NFA to DFA33:49
Converting NFA to DFA
Converting Nondeterministic Finite Automaton to an Equivalent Deterministic Finite Automaton
Construction of a Finite Automaton45:53
Construction of a Finite Automaton
Designing Finite Automaton for Given Language
Designing DFA for Given Language
Designing NFA for Given Language
Finite Automata with Outputs, Moore Machine, Mealy Machine27:48
Finite Automata with Outputs
Moore Machine
Mealy Machine
Difference between Moore Machine and Mealy Machine
Conversion of Moore Machine to Equivalent Mealy Machine12:18
Conversion of Moore Machine to Equivalent Mealy Machine
Finite Automata with Outputs, Moore Machine, Mealy Machine
Conversion of Mealy Machine to Equivalent Moore Machine18:55
Conversion of Mealy Machine to Equivalent Moore Machine
Finite Automata with Outputs, Moore Machine, Mealy Machine
Minimization of Finite Automata1:10:18
Minimization of Finite Automata
0-level Equivalence
1-level Equivalence
2-level Equivalence
3-level Equivalence
DFA corresponding to 3-level Equivalence
Example - Minimization of Finite Automata40:03
Example - Minimization of Finite Automata
0-level Equivalence
1-level Equivalence
2-level Equivalence
3-level Equivalence
DFA corresponding to 3-level Equivalence
Minimum State Finite Automata
Section 1: Practice Examples0:16

Regular Expression, Regular Set, Regular Language, Finite Automata21:32
Regular Expression
Regular Set
Regular Language
Finite Automata
Correspondence between Regular Expression and Regular Set10:00
Correspondence between Regular Expression and Regular Set
Regular Expression
Regular Set
Regular Language
Example: Correspondence between Regular Expression and Regular Set20:04
Example: Correspondence between Regular Expression and Regular Set
Regular Expression
Regular Set
Regular Language
Identifying Regular Set from Regular Expression
Identifying Regular Language from Regular Expression L(R)
Examples: Regular Expression for Regular Set or Regular Language33:13
Examples: Regular Expression for Regular Set or Regular Language
Regular Expression, Regular Set, Regular Language
Identifying Regular Expression from Regular Set
Identifying Regular Expression from Regular Language
Examples: Regular Expression for Regular Set or Regular Language32:13
Examples: Regular Expression for Regular Set or Regular Language
Regular Expression, Regular Set, Regular Language
Identifying Regular Expression from Regular Set
Identifying Regular Expression from Regular Language
Identifying Finite Automaton from Regular Expression
Examples: Regular Expression, Regular Set, Regular Language19:45
Examples: Regular Expression, Regular Set, Regular Language
Identifying Minimum Length String which does not Corresponds to given Regular Expression, Regular Expression, Regular Set, Regular Language
Identifying Regular Expression from Regular Set
Identifying Regular Expression from Regular Language
Identifying Finite Automaton from Regular Expression
Examples: Finite Automaton Corresponding to given Regular Expression14:29
Examples: Finite Automaton Corresponding to given Regular Expression
Regular Set, Regular Language, Regular Expression
Identifying Regular Expression from Regular Set
Identifying Regular Expression from Regular Language
Identifying Finite Automaton from Regular Expression
Transition System Containing Ԑ- Moves21:49
Transition System Containing Ԑ- Moves
Eliminating Ԑ- Moves
Eliminating Null Moves from Finite Automaton
Obtaining an Equivalent Finite Automaton without Ԑ- Moves
Eliminating Ԑ- Moves6:55
Transition System Containing Ԑ- Moves
Eliminating Ԑ- Moves
Eliminating Null Moves from Finite Automaton
Obtaining an Equivalent Finite Automaton without Ԑ- Moves
Arden's Theorem28:55
Arden's Theorem
Conditions for Applying Arden's Theorem
Identifying Regular Expression from Finite Automaton using Arden's Theorem
Arden's Theorem: Finding Regular Expression from Finite Automaton18:38
Arden's Theorem
Finding Regular Expression from Finite Automaton
Describing Language of Finite Automaton
Examples
Equivalence of Two Finite Automata19:28
Equivalence of Two Finite Automata
Comparison Method to Test Equivalence of Two Finite Automata
Example: Equivalence of Two Finite Automata6:21
Example: Equivalence of Two Finite Automata
Comparison Method to Test Equivalence of Two Finite Automata
Closure Properties of Regular Languages1:01:38
Closure Properties of Regular Languages
Closure Properties of Regular Sets
Finite Automaton for Union of Languages
Finite Automaton for Intersection of Languages
Finite Automaton for Difference of Languages
Finite Automaton for Concatenation of Languages12:53
Closure Properties of Regular Languages
Closure Properties of Regular Sets
Finite Automaton for Concatenation of Languages
Finite Automaton for Transpose of a Language and Reverse of a Language10:52
Finite Automaton for Transpose of a Language
Finite Automaton for Reverse of a Language
Closure Properties of Regular Languages
Closure Properties of Regular Sets,
Finite Automaton for Complement of a Language4:51
Finite Automaton for Complement of a Language
Closure Properties of Regular Languages
Closure Properties of Regular Sets
Finite Automaton for Kleen's Star of a Language10:12
Closure Properties of Regular Languages
Closure Properties of Regular Sets
Finite Automaton for Kleen's Star of a Language
Regular Grammar, Construction of a Regular Grammar Generating L(M)36:46
Regular Grammar
Construction of a Regular Grammar Generating L(M) for a given DFA M
Construction of a Transition System M Accepting L(G) for a given Regular Grammar16:43
Construction of a Transition System M Accepting L(G) for a given Regular Grammar
Construction of a DFA for a given Regular Grammar
Section 2: Practice Examples0:13
Regular Expression and Regular Grammar: Definition and Identities of Regular Expressions, Construction of Regular Expression of the given Language, Construction of Language from the RE, Conversion of FA to RE using Arden’s Theorem, Inter-conversion RE to FA, Pumping Lemma for RL, Closure properties of RLs, Regular grammar, Equivalence of RG ( RLG and LLG) and FA

Context Free Grammars29:03
Context Free Grammars
Context Free Languages
Constriction of Context Free Grammar for generating all Sign Integers
Derivation Trees, Context Free Grammars16:05
Derivation Trees
Context Free Grammars
Leftmost Derivation, Rightmost Derivation, Derivation Trees24:25
Leftmost Derivation
Rightmost Derivation
Derivation Trees
Context Free Grammar
Ambiguity in Context Free Grammars, Ambiguous Context Free Grammar22:32
Ambiguity in Context Free Grammars
Ambiguous Context Free Grammar
Ambiguous String
Designing Context Free Grammar for the given Language21:54
Designing Context Free Grammar for the given Language
Construction of Context Free Grammar for given Language
Chomsky Classification of Grammar23:05
Chomsky Classification of Grammar
Type 3 Grammar, Type 2 Grammar, Type 1 Grammar, Type 0 Grammar
Regular Grammar, Context Free Grammar, Context Sensitive Grammar, Unrestricted Grammar
Finite Automaton, FA, DFA, NFA, PDA, LBA, TM
Construction of Reduced Grammars: Part 133:23
Construction of Reduced Grammars: Part 1
Obtaining an Equivalent Grammar of a Context Free Grammar such that every Variable in CFG derives a terminal string
Eliminating Variables not deriving any terminal Symbol
Construction of Reduced Grammars: Part 221:25
Construction of Reduced Grammars: Part 2
Obtaining an Equivalent Grammar of a Context Free Grammar such that every symbol in CFG appears in some sentential form
Eliminating symbols which are not reachable from the start variable
Construction of Reduced Grammars: Part 330:15
Construction of Reduced Grammars: Part 3
Obtaining an Equivalent Grammar of a Context Free Grammar such that every Variable in CFG derives a terminal string
Eliminating Variables not deriving any terminal Symbol
Obtaining an Equivalent Grammar of a Context Free Grammar such that every symbol in CFG appears in some sentential form
Eliminating symbols which are not reachable from the start variable
Elimination of Null Productions20:16
Elimination of Null Productions
Elimination of Null Productions from Context Free Grammar
Constructing Set of Nullable Variables
Elimination of Unit Productions from Context Free Grammar34:52
Elimination of Unit Productions from Context Free Grammar
Set of variables derivable from given variable
Reduction to Chomsky Normal Form26:34
Reduction to Chomsky Normal Form
Converting context free grammar to Chomsky normal form
Eliminating terminals from right hand side, restricting number of variables on right hand side, restricting number of non terminals on right hand side
Greibach Normal Form39:53
Greibach Normal Form
Converting given grammar to Greibach Normal Form
Lammas for obtaining Greibach Normal Form
Section 3: Practice Examples0:09

Designing Pushdown Automata for given Context Free Language34:09
Pushdown Automata
Designing Pushdown Automata for given Context Free Language
String Processing on Push Down Automata
Acceptance by Null Store in PDA
Acceptance by Final State in PDA
Examples on Push Down Automata37:30
Designing Push Down Automata for given Context Free Language
Examples on Push Down Automata
String Processing on Push Down Automata
Obtaining PDA from CFG38:58
Pushdown Automata
Acceptance by Null Store
Acceptance by Final State
Pushdown Automata from Context Free Grammar
Obtaining PDA from CFG
Nondeterministic Pushdown Automata NPDA
Deterministic Pushdown Automata, DPDA
Obtaining Context Free Grammar from Pushdown Automata56:54
Obtaining Context Free Grammar from Pushdown Automata
Productions Corresponding to Push Operations
Productions Corresponding to Pop Operations
Productions Corresponding to Transitions
GATE Questions35:03
Pushdown Automata
Context Free Language
Context Free Grammar
Chomsky Classification
Objective Questions
GATE Questions
Section 4: Practice Examples0:08

Turing Machine, Turing Machine Model, String Processing in Turing Machine35:59
Turing Machine, Turing Machine Model, String Processing in Turing Machine
Designing a Turing Machine for given Language31:18
Turing Machine, Processing Strings on Turing Machine
Strings Acceptability in Turing Machine
Designing a Turing Machine for given Language
Turing Machine for Even Number of 1s, Turing Machine for Odd Number of 1s
Designing Turing Machine for Given Language40:51
Turing Machine for Concatenation of String
Turing Machine for Multiple of Three
Turing Machine for Strings with Equal Number of Zeros and Ones
Designing Turing Machine for Given Language42:58
Turing Machine for Addition of Two Positive Integers
Turing Machine for Language Containing Stings followed by Reverse of Same String
Turing Machine for String Containing Number of Zeros followed by Twice Number of Ones
Designing a Turing Machine40:48
Turing Machine for Subtraction of Two Positive Integers
Turing Machine for Dividing Positive Integer by 3
Turing Machine for Identifying Quotient and Reminder
Linear Bounded Automata, Model of Linear Bounded Automata28:03
Linear Bounded Automata
Model of Linear Bounded Automata
Designing Linear Bounded Automata for Given Language
Tuples for Linear Bounded Automata
Obtaining Grammar for Turing Machine, Obtaining Grammar for LBA38:16
Obtaining Grammar for Turing Machine
Obtaining Grammar for Linear Bounded Automata
Process for Construction of Type 0 and Type 1 Grammar
Obtaining Type 0 Grammar for Turing Machine
Obtaining Type 1 Grammar for Linear Bounded Automata
Inverse Production Rules for Turing Machine
Inverse Production Rules for Linear Bounded Automata
Section 5: Practice Examples0:06

Recursive and Non Recursive Languages33:22
Recursive and Non Recursive Languages
Recursive Enumerable Languages
Types of Turing Machine
Universal Turing Machine
Decidability, Undecidability, Solvable Problem, Unsolvable Problem
Church Turing Hypothesis
Algorithm
Computational Problem
Post Correspondence Problem, PCP, Finding whether the PCP has a solution16:47
Post Correspondence Problem, PCP, Finding whether the PCP has a solution
MPCP
Primitive Recursive Functions, Recursive Function Theory, Initial Functions46:01
Primitive Recursive Functions
Recursive Function Theory
Initial Functions
Finding Whether given Function is Recursive or Not
Zero Function, Successor Function, Projection Function
Composition of Functions
Section 6: Practice Examples0:07

Requirements

No experience needed. You will learn everything you need to know.

Description

Finite State Machines: Alphabet, String, Formal and Natural Language, Operations, Definition and Design DFA (Deterministic Finite Automata), NFA (Non Deterministic Finite Automata), Equivalence of NFA and DFA: Conversion of NFA into DFA, Conversion of NFA with epsilon moves to NFA, Minimization of DFA, Definition and Construction of Moore and Mealy Machines, Inter-conversion between Moore and Mealy Machines. Minimization of Finite Automata. (Construction of Minimum Automaton)

Regular Expression and Regular Grammar: Definition and Identities of Regular Expressions, Construction of Regular Expression of the given Language, Construction of Language from the RE, Conversion of FA to RE using Arden’s Theorem, Inter-conversion RE to FA, Pumping Lemma for RL, Closure properties of RLs, Regular grammar, Equivalence of RG ( RLG and LLG) and FA

Context Free Grammar and Languages: Introduction, Formal Definition of Grammar, Notations, Derivation Process: Leftmost Derivation, Rightmost Derivation, Derivation Trees, Construction of Context-Free Grammars and Languages, Pumping Lemma for CFL, Simplification of CFG, Normal Forms (CNF and GNF), Chomsky Hierarchy

Pushdown Automata: Introduction and Definition of PDA, Construction of PDA, Acceptance of CFL, Equivalence of CFL and PDA: Inter-conversion , Introduction of DCFL and DPDA, Enumeration of properties of CFL, Context Sensitive Language, Linear Bounded Automata

Turing Machines: Formal definition of a Turing Machine, Design of TM, Computable Functions, Church’s hypothesis, Counter machine, Variants of Turing Machines: Multi-tape Turing machines, Universal Turing Machine

Decidability and Un-Decidability: Decidability of Problems, Halting Problem of TM, Un-Decidability: Recursive enumerable language, Properties of recursive & non-recursive enumerable languages, Post Correspondence Problem, Introduction to Recursive Function Theory

Who this course is for:

Undergraduate and Post Graduate Students

Theory of Computation

What you'll learn

Explore related topics

Course content

Finite State Machines20 lectures • 8hr 31min

Regular Expression and Regular Grammar21 lectures • 6hr 48min

Context Free Grammar and Languages14 lectures • 5hr 44min

Pushdown Automata6 lectures • 3hr 23min

Turing Machines8 lectures • 4hr 18min

Decidability and Un-Decidability4 lectures • 1hr 36min

Requirements

Description

Who this course is for: