Teach on Udemy

Turn what you know into an opportunity and reach millions around the world.

Learn More

Your cart is empty.

Keep shopping

Formal Languages and Automata Theory

Name: Formal Languages and Automata Theory
Rating: 4.3 (692 reviews)

Introduction to Automata Theory, Languages and Computation

Created byProf Madana Mohana R

Last updated 10/2026

English

What you'll learn

Apply formal notation to represent alphabets, strings, languages, grammars, and computational machines.
Design finite automata and regular expressions to recognize regular languages and apply closure and equivalence properties.
Construct CFGs and PDAs to generate and recognize context-free languages and convert grammars into normal forms.
Understand the hierarchy of formal languages, grammars, and machines, and analyze the relationships and equivalence between different computational models.
Analyze Turing machines, computability, and decidability, distinguishing computable from non-computable and decidable from undecidable problems.

Course content

15 sections • 64 lectures • 40h 23m total length

Introduction to Automata Theory58:20
Introduction to Automata Theory or Theory of Computation
Applications of Automata Theory or Theory of Computation
Basic Fundamentals /Central Concepts of Automata Theory
Fundamental Concepts of Automata Theory and Chomsky Hierarchy1:19:23
Basic Fundamentals /Central Concepts of Automata Theory
Language - Language Operations
Formal Language
Grammar or Formal Grammar
Problems
Formal Languages and Chomsky Hierarchy
Introduction to Finite Automata (FA)1:06:55
OUTLINE:
Introduction to Finite Automata (FA)
Model of FA
Formal Definition of FA
Example of FA
Transition Table of FA
Transition Diagram of FA
Example Problems on FA
Finite Automata (FA): Acceptance, Structural Representations and Complexity36:25
OUTLINE:
Acceptance of Strings and Languages by FA
Structural Representations: Grammars and Regular Expressions
Automata and Complexity: Decidability and Intractability
Deterministic Finite Automata (DFA)34:38
OUTLINE:
Definition of DFA
How a DFA Processes Strings
Simpler Notations for DFA’s
Extending the Transition Function to Strings
The Language of DFA
Nondeterministic Finite Automata (NFA)34:52
OUTLINE:
Introduction to NFA
Definition of NFA
Extended Transition Function
The Language of NFA
Equivalence of NFA and DFA59:33
OUTLINE:
Equivalence of NFA and DFA
An Application: Text Search

Finite Automata with Epsilon Transitions (NFA-ϵ)29:40
OUTLINE:
Finite Automata with Epsilon-Transitions(NFA-ϵ)
Uses of ϵ-Transitions
The Formal Notation for an ϵ-NFA
Epsilon-Closures
Extended Transitions and Languages for ϵ-NFA’s
Acceptance of Strings and Languages by ϵ-NFA
Equivalence of NFA with and without ϵ-moves (Eliminating ϵ-transitions)43:07
OUTLINE:
Equivalence of NFA with and without ϵ-moves (Eliminating ϵ-transitions)
Eliminating ϵ-Transitions (Conversion of NFA with ԑ-transitions to NFA without ϵ-transitions)
Example Problems
Conversion of NFA-ϵ (with epsilon) to DFA23:10
OUTLINE:
Conversion of NFA-ϵ (with epsilon) to DFA
Conversion of NFA-ϵ (with epsilon) to Direct DFA
Example Problems

Introduction to Moore and Mealy machines22:24
OUTLINE:
Finite Automata with output
Moore Machine-Definition, Example
Mealy Machine-Definition, Example
Conversion of Mealy machine to Moore machine21:45
OUTLINE:
Moore Machine
Mealy Machine
Equivalence of Moore and Mealy machines
Conversion of Mealy to Moore machine
Conversion of Moore machine to Mealy machine17:37
OUTLINE:
Moore Machine
Mealy Machine
Equivalence of Moore and Mealy machines
Conversion of Moore machine to Mealy machine

Introduction to Regular Expressions32:29
Explore the introduction to regular expressions, their algebraic laws, and applications, and learn how finite automata relate to regular expressions through union, concatenation, and star operations.
Regular Expressions: Algebraic Laws & Applications37:17
Demonstrate algebraic laws of regular expressions to simplify and prove equivalence, and apply them to Unix patterns, lexical analysis, and text pattern finding.
Conversion of Regular Expression to Finite Automata (FA)35:14
OUTLINE:
Equivalence of Regular Expressions and Finite Automata (FA)
Kleens Theorem
Conversion of Regular Expressions to NFA with epsilon moves
Conversion of Finite Automata (FA) to Regular Expression31:55
OUTLINE:
Equivalence of Regular Expressions and Finite Automata (FA)
Kleens Theorem
Conversion of Finite Automata (FA) to Regular Expression

Pumping Lemma for Regular Sets / Regular Languages35:16
OUTLINE:
Introduction to Pumping Lemma
Statement of Pumping Lemma
Applications of Pumping Lemma
Example problems on Pumping Lemma
Closure Properties & Decision Properties for Regular Sets / Regular Languages34:08
OUTLINE:
Closure Operation
Closure Property
Closure Properties for Regular Sets / Regular Languages
Decision Properties for Regular Sets / Regular Languages
Converting among Regular Expressions

Equivalence between two Finite State Machines (FSMs) / Finite Automatons (FAs)38:22
OUTLINE:
FSM Equivalence
FSM Equivalence Algorithm
FSM Equivalence -Example Problems
Minimization of Deterministic Finite Automata (DFA)47:31
OUTLINE:
Minimization of Deterministic Finite Automata (DFA) part-1
Minimization of Finite State Machine (FSM) / Deterministic Finite Automata (DFA)
Myhill Nerode Theorem
Distinguishable and indistinguishable states
Minimization Algorithm: Table filling algorithm
Example problems
Construction of Minimized DFA15:16
OUTLINE:
Minimization of Deterministic Finite Automata (DFA) part-2
Minimization of Finite State Machine (FSM) / Deterministic Finite Automata (DFA)
Myhill Nerode Theorem
Distinguishable and indistinguishable states
Minimization Algorithm: Table filling algorithm
Example problems

Introduction to Regular Grammars24:05
OUTLINE:
Definition of Formal Grammar
Left-linear and Right-linear grammars
Regular Grammars
Examples
Regular Grammars and Finite Automata (FA)35:50
OUTLINE:
Definition of Formal Grammar
Left-linear and Right-linear grammars
Regular Grammars
Regular Grammars and Finite Automata
Conversion of Regular Grammars to Finite Automata
Conversion of Finite Automata to Regular Grammars
Example problems

Introduction to Context-free Grammars (CFG's)47:28
OUTLINE:
Definition of Context-Free Grammars
Derivations Using a Grammar
Leftmost and Rightmost Derivations
The Language of a Grammar
Sentential Forms
Context-free Grammars (CFG's): Parse Tree/Derivation Tree & Applications of CFGs41:09
OUTLINE:
Parse Tree or Derivation Tree
Applications of CFGs: Parser and Markup Languages
Context free Grammars (CFG's): Ambiguity46:47
OUTLINE:
Ambiguity in Grammars and Languages
Ambiguous Grammar
Example problems on ambiguous grammars
Context free Grammars (CFG's): Eliminating Ambiguity38:25
OUTLINE:
Ambiguity in Grammars and Languages
Ambiguous Grammar
Eliminating Ambiguity in CFGs
Example problems on ambiguous grammars

Introduction to Pushdown Automata (PDA)43:52
OUTLINE:
Introduction of PDA
Model of PDA
Formal Definition of PDA
Instantaneous Description (ID) of PDA
Example of PDA
Graphical Notations for PDA: Transition Table & Transition Diagram
Accepted Languages of PDA
Pushdown Automata (PDA)-Acceptance of Languages by Final State & Empty Stack24:12
OUTLINE:
Accepted Languages of PDA
Acceptance of Languages by Final State of PDA
Acceptance of Languages by Empty Stack or Null Stack of PDA
Acceptance of Languages by both Final State and Empty Stack or Null Stack of PDA
Example problems with solutions
Design of PDA for CFL part-143:27
OUTLINE:
Design of PDA for the given CFL
Pushdown Automata (PDA)
Context Free Language (CFL)
Example problem-1
Design of PDA for CFL part-235:54
OUTLINE:
Design of PDA for the given CFL
Pushdown Automata (PDA)
Context Free Language (CFL)
Example problem-2
Equivalence of PDA's and CFG's: Conversion of CFG to PDA40:26
OUTLINE:
Equivalence of PDA’s and CFL’s
Equivalence of PDA's and CFG's
Conversion of CFG to PDA
Pushdown Automata (PDA)
Context Free Language (CFL)
Example Problem
Equivalence of PDA's and CFG's: Conversion of CFG to PDA41:55
OUTLINE:
Equivalence of PDA’s and CFL’s
Equivalence of PDA's and CFG's
Conversion of PDA to CFG
Example Problem
Deterministic Pushdown Automata (DPDA)36:02
OUTLINE:
Deterministic Pushdown Automata (DPDA) Definition
DPDA Conditions
Checking whether a PDA is DPDA or not
DPDA Example Problems
Deterministic Context Free Language (DCFL)
Relation of Regular Language, CFL and DCFL
Prefix property of CFL

Normal Forms for CFGs: Removing useless symbols & useless productions38:09
OUTLINE:
Normal forms for CFGs
A useful substitution rule
Removing useless symbols
Removing useless productions
Example problems
Normal forms for CFG: Removing Null Productions & Unit Productions54:58
OUTLINE:
Normal forms for CFGs
Removing Null productions
Removing Unit productions
Example problems
Normal forms for CFG: Chomsky Normal Form (CNF)46:52
OUTLINE:
Normal forms for CFGs
Removing Null productions
Removing Unit productions
Removing Useless symbols and useless productions
Chomsky Normal Form (CNF): Definition
Reducing a CFG to Chomsky Normal Form (CNF)
Solving Example Problem
Normal Forms for CFG- Greibach Normal Form (GNF)50:03
OUTLINE:
Normal forms for CFGs
Chomsky Normal Form (CNF)
Reducing a CFG to Chomsky Normal Form (CNF)
Greibach Normal Form (GNF): Definition
Reducing a CFG to Greibach Normal Form (GNF)
Solving Example Problems

Requirements

Basic knowledge of Computer Science fundamentals is recommended.
Familiarity with discrete mathematics, sets, relations, functions, and basic logic will be helpful.
Basic understanding of algorithms and programming concepts is useful but not mandatory.
No prior knowledge of Formal Languages and Automata Theory is required.
A willingness to learn mathematical concepts and solve problems is all you need to get started.

Description

Formal Languages and Automata Theory is a fundamental area of theoretical Computer Science that explores formal languages, grammars, automata, computation, algorithms, computability, decidability, and complexity.

Automata Theory provides an elegant and systematic way to understand the capabilities and limitations of computational machines. The concepts have lasting relevance despite the rapid evolution of computing technologies and continue to provide foundations for compiler design, programming languages, pattern matching, circuit design, cybersecurity, optimization, and computational problem solving.

This course provides a structured introduction to the theoretical foundations of Computer Science from the perspective of formal languages and computational models. Learners will progressively explore finite automata, regular languages, regular expressions, context-free grammars, pushdown automata, Turing machines, and the hierarchy of formal languages.

Throughout the course, learners will develop the ability to design and analyze computational models, classify machines according to their language-recognition capabilities, and reason about computability and decidability.

By the end of this course, learners will be able to:

• Explain the fundamental concepts of formal languages, grammars, and automata theory.

• Design and analyze deterministic and non-deterministic finite automata for computational problems.

• Apply regular expressions and regular language properties to model and solve problems.

• Construct and analyze context-free grammars and pushdown automata.

• Understand Turing machines, computability, decidability, and undecidability.

• Classify computational models according to the power of languages they recognize.

• Develop a strong theoretical foundation for further study in Computer Science, programming languages, compilers, and related fields.

Who this course is for:

Computer Science and IT students studying Formal Languages and Automata Theory or related subjects.
Undergraduate and postgraduate students preparing for university examinations and competitive examinations.
Students preparing for technical interviews who want to strengthen their theoretical Computer Science fundamentals.
Faculty, researchers, and computing professionals seeking to refresh their knowledge of formal languages, automata, and computational theory.
Anyone interested in understanding the mathematical and theoretical foundations of computation, programming languages, and computer systems.

Formal Languages and Automata Theory

What you'll learn

Explore related topics

Course content

Introduction to Finite Automata7 lectures • 6hr 10min

Finite Automata with Epsilon Transitions (NFA-ϵ)3 lectures • 1hr 36min

Finite Automata with Output: Moore and Mealy Machines3 lectures • 1hr 2min

Regular Expressions and Regular Languages4 lectures • 2hr 17min

Pumping Lemma and Closure Properties of Regular Languages2 lectures • 1hr 9min

Equivalence and Minimization of Finite Automatons (FAs)3 lectures • 1hr 41min

Regular Grammars and Finite Automata (FA)2 lectures • 1hr

Context-Free Grammars4 lectures • 2hr 54min

Push Down Automata7 lectures • 4hr 26min

Normal Forms for Context- Free Grammars4 lectures • 3hr 10min

Requirements

Description

Who this course is for: