Introduction to Automata Theory, Languages and Computation

Name: Introduction to Automata Theory, Languages and Computation
Rating: 3.8 (216 reviews)

Theory of computation, Automata Theory, Formal Language and Automata Theory

Created byDr.Deeba K

Last updated 8/2025

English

What you'll learn

Understand the basics of Automata Theory, Languages and its need
Understand the working of Finite Automata, Push Down Automata and Turing Machine
Able to solve problems using Finite Automata, Push Down Automata and Turing Machine
Able to recognize the relationship between various Automata
Understand the need for proving various equivalence between Automata

Course content

12 sections • 84 lectures • 19h 51m total length

Introduction to this course4:15
Introduction to Automata - Languages - Chomsky Hierarchy10:02
Formal Languages: Strings, Languages10:29
Chomsky Hierarchy10:59
Trace the Chomsky hierarchy from finite automata to Turing machines, and learn how regular, context-free, context-sensitive, and unrestricted languages are distinguished by grammar representations and memory.
Introduction

Introduction to Finite Automata12:12
DFA and NFA18:01
Compare nondeterministic and deterministic finite automata, focusing on transition functions and state machines. Learn how NFA and DFA differ in acceptance and language recognition.
DFA - Extended Transition Function and Language Acceptance7:50
NFA - Extended Transition Function and Language Acceptance9:03
Examples of DFA and NFA - language of strings29:25
Example DFA for complement of any language8:19
Finite Automaton with €- moves3:09
Explore epsilon moves in finite automata and how epsilon NFAs transition without input, using states for zero or more a's, b's, and c's, and preparing for conversion techniques.
Finite Representation : Regular Expressions (RE)10:58
Explore how regular expressions express regular languages with union, concatenation, and Kleene star, and how to convert between NFA and DFA; apply to lexical analysis and identifier recognition.
Pumping Lemma for RE10:17
Explore the pumping lemma for regular languages, showing how a finite automaton via the pigeonhole principle yields a u, v, w split with a loop to prove non-regular languages.
Finite Automata

Equivalence of NFA, DFA, NFA with €- moves and RE4:26
Working and examples for Subset construction Method15:48
NFA to DFA using Lazy subset construction Method7:48
Thomson's Construction Method for RE to Ꜫ-NFA6:54
Regular Expression to DFA20:39
Solved Examples for RE to DFA13:38
Minimization of DFA21:03
Epsilon NFA to NFA20:16
Learn to convert an epsilon NFA to an NFA by computing epsilon closures and building a transition table for A, B, C with inputs P, Q, R.
DFA to RE (Formula Method)14:07
Solved Examples for DFA to RE (Formula Method)16:27
Solved Examples for DFA to RE 3 states (Formula method)15:53
DFA to RE (State Elimination Method)17:31
Finite Automata - Example 1 - Scenario Question4:33
Finite Automata - Example 2 - Scenario based question9:51
Finite Automata - Example 3 - Scenario based question for DFA construction6:53
Equivalence of Finite Automata

Introduction to Moore and Mealy Machine16:52
Explore Moore and Mealy machines, two variants of finite automata with output, where Mealy outputs depend on state and input, and Moore outputs depend on state, highlighting their equivalence.
Moore machine Example and Three ways of representation10:55
Demonstrates Moore machines that output one for every a followed by b, contrasts with DFA, and teaches three representations: transition diagram, transition table, and six-tuple notation.
Mealy machine Example and Three ways of representation10:49
Moore Machine to Mealy Machine4:35
Mealy machine to Moore machine11:27

Introduction, Types of Grammar and Representation9:42
Context Free Grammar (CFG) and Languages9:49
Learn how context free grammar defines languages with productions like alpha -> beta, distinguishing variables and terminals, and starting from a symbol to derive palindromes and A^n B^n patterns.
Example 1: CFG construction11:17
Example 2: CFG construction11:14
Explore context-free grammar construction for programming constraints, including declarative statements, if-then-else, and while statements, and learn CFG components such as variables, terminals, starting symbol, and production rules.
Example 3: CFG construction9:11
Derive context-free grammars for regular expressions, linking regular languages to pushdown automata, and use start symbols, variables, terminals, and productions to capture Kleene closures and epsilon.
Derivation, Parse tree and Ambiguity18:09
Simplification of CFG - Elimination of Useless Symbols10:35
Simplification of CFG - Elimination of Null productions7:51
Simplification of CFG - Elimination of Unit productions3:10
CFG to Chomsky Normal Form (CNF)12:33
Scenario based example for CNF20:52
Explore a scenario based example of a context free grammar and its conversion to Chomsky normal form, including terminals, nonterminals, parse trees, and leftmost and rightmost derivations.
Solved Examples - CFG to CNF11:25
CFG to Greibach Normal form13:22
Solved Examples - CFG to GNF19:08
Solved Examples - CNF to GNF6:15
Scenario GNF15:52
Example 1 - Scenario based question for CNF and GNF24:09
Context Free Grammar

Introduction to Push Down Automata8:01
Problem in PDA {a^nb^n/n>1}12:47
Show how a pushdown automaton accepts the language a^n b^n (n≥1) by using a stack, pushing a's and popping with b's, with a bottom symbol z0.
Problem in PDA {a^n b^ m/n,m>=1} two problems (n>m) and (m>n)12:46
Problem in PDA { WCW^R/ w={a,b}*}19:20
Non-Deterministic PDA {Palindrome of a string}14:57
CFG (Context Free Grammar) to PDA (Push Down Automata)18:24
PDA (Push Down Automata) to CFG (Context Free Grammar)20:35
Convert a pushdown automaton to a context free grammar by mapping states and stack symbols to grammar variables and transitions to production rules, including the starting symbol and epsilon transitions.
Pumping Lemma for CFG7:20
Scenario based question in CFG and PDA25:26
Push Down Automata

Introduction to Turing Machine, Instantaneous Description17:10
Explore how a Turing machine uses an infinite tape, read/write head, and transition diagrams to perform computations, with ID descriptions, states, and acceptance or rejection processes.
Turing Machine Representations27:35
Turing Machine for Regular Language19:10
Turing Machine for Context Free Language13:11
TM for L={a^n b^n c^n / n>=0}10:01
TM for palindrome of a string over alphabet a,b26:03
TM for proper subtraction24:25
TM for Multiplication24:32
Modifications of TM14:34
Simulation of Turing Machine10:15
Explore an online Turing machine simulator to model, implement, and verify a Turing machine; define transitions, states, and input rules, and test acceptance or rejection.
Turing Machine

Example 1 : Regular Language - construction of DFA, PDA and TM15:42
Example 2 : Context Free Language - Construction of PDA and TM23:12
explains how to construct a pushdown automaton and a turing machine for the context-free language a^n b^{2n}, outlining stack-based memory, transitions, and acceptance.
Example 3 : Turing Machine problem17:00
Example 4 : Turing Machine for 1's Complement3:41
Design a Turing machine to compute one's complement by flipping zeros to ones and ones to zeros on the input tape, scanning left to right and accepting at blank.
Example 5 : scenario based question in Turing Machine9:11
Example 6 : scenario based question in Turing Machine34:58
Example 7 : scenario based question in Turing Machine18:32
Example 8 : scenario based question in PDA and CFG13:18

Requirements

No prerequisites are there for this course. Students can listen to the lectures to understand Automata Theory concepts from base.

Description

The aim of this course “Introduction to Automata Theory, Languages and Computation” is to give a detailed working explanation regarding each Mathematical model, its corresponding languages, and their provable equivalence. “Theory of Computation” has three major subdivisions namely

1) Automata Theory

2) Computability Theory

3) Complexity Theory

The automata theory deals with some Mathematical models that perform some operations automatically like programming machines. There are four main Mathematical models namely, Finite Automata(FA), Push Down Automata(PDA), Linear Bound Automata(LBA), and Turing Machine(TM). Each Mathematical model differs based on its memory units as FA has no external memory unit, PDA has stack as a memory unit, LBA has finite length tape as a memory unit and TM has infinite tape as a memory unit.

Based on the limitations in the memory unit each model solves a limited set of problems only. The set of problems solved by each model is grouped as languages accepted by the model. The problems solved by Finite Automata are called Regular Language and its corresponding language representation is called Regular Grammar. The language accepted by Push Down Automata is called Context Free Language, the language accepted by Linear Bound Automata is called Context Sensitive Language, and the language accepted by Turing Machine is called Un-Restricted language since Turing machines have unlimited memory and random access to the memory unit.

Turing machines can be equated to modern computers, it can solve any problem that is solvable by computers. Computability theory deals with verifying whether the problem is solvable or not and If it is solvable complexity theory deals with the algorithmic complexity of problems that are solvable by Turing Machine.

This course mainly deals with automata theory (Mathematical Models) and its languages.

Who this course is for:

Computer science students
Students preparing for Gate exams
Anyone planning for Government Exams in Computer Science base
Students interested in understanding the basic working of Models

Introduction to Automata Theory, Languages and Computation

What you'll learn

Explore related topics

Course content