Formal Languages and Automata Theory

Name: Formal Languages and Automata Theory
Rating: 4.7 (598 reviews)

Introduction to Automata Theory, Languages and Computation

Highest Rated

Created byProf Madana Mohana R

Last updated 8/2024

English

What you'll learn

Develop a formal notation for strings, languages and machines.
Design finite automata to accept a set of strings of a language.
Prove that a given language is regular and apply the closure properties of languages.
Design context free grammars to generate strings from a context free language and convert them into normal forms.
Prove equivalence of languages accepted by Push Down Automata and languages generated by context free grammars.
Identify the hierarchy of formal languages, grammars and machines
Distinguish between computability and non-computability and Decidability and undecidability.

Course content

15 sections • 59 lectures • 37h 5m 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
Regular Expressions: Algebraic Laws & Applications37:17
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

Mathematical Foundations of Computer Science
Data structures and Algorithms
Database Management System

Description

Formal Languages and Automat Theory deals with the concepts of automata, formal languages, grammar, algorithms, computability, decidability, and complexity.
The reasons to study Formal Languages and Automat Theory are Automata Theory provides a simple, elegant view of the complex machine that we call a computer.
Automata Theory possesses a high degree of permanence and stability, in contrast with the ever-changing paradigms of the technology, development, and management of computer systems. Further, parts of the Automata theory have direct bearing on practice, such as Automata on circuit design, compiler design, and search algorithms; Formal Languages and Grammars on compiler design; and Complexity on cryptography and optimization problems in manufacturing, business, and management.
The purpose of this course is to acquaint the student with an overview of the theoretical foundations of computer science from the perspective of formal languages.

At the end of the course, the students will be able to:

Provide introduction to some of the central ideas of theoretical computer science from the perspective of formal languages.
Introduce the fundamental concepts of formal languages, grammars and automata theory.
Classify machines by their power to recognize languages.
Employ finite state machines to solve problems in computing.
Understand deterministic and non-deterministic machines.
Understand the differences between decidability and undecidability.

Who this course is for:

Engineering-Undergraduate/Postgraduate

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: