Introduction to Finite Automata

Introduction to Automata Theory

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 Hierarchy

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)

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 Complexity

Outline:
- Acceptance of Strings and Languages by FA
- Structural Representations: Grammars and Regular Expressions
- Automata and Complexity: Decidability and Intractability

Deterministic Finite Automata (DFA)

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)

Outline:
- Introduction to NFA
- Definition of NFA
- Extended Transition Function
- The Language of NFA

Equivalence of NFA and DFA

Outline:
- Equivalence of NFA and DFA
- An Application: Text Search

Finite Automata with Epsilon Transitions

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 Epsilon Moves (Eliminating Epsilon Transitions)

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 Epsilon (with epsilon) to DFA

Outline: Conversion of NFA-ϵ (with epsilon) to DFA
- Conversion of NFA-ϵ (with epsilon) to Direct DFA
- Example Problems

Finite Automata with Output: Moore and Mealy Machines

Introduction to Moore and Mealy machines

Outline:
- Finite Automata with output
- Moore Machine-Definition, Example
- Mealy Machine-Definition, Example

Conversion of Mealy machine to Moore machine

Outline:
- Moore Machine
- Mealy Machine
- Equivalence of Moore and Mealy machines
- Conversion of Mealy to Moore machine

Conversion of Moore machine to Mealy machine

Outline:
- Moore Machine
- Mealy Machine
- Equivalence of Moore and Mealy machines
- Conversion of Moore machine to Mealy machine

Regular Expressions and Regular Languages

Introduction to Regular Expressions

Regular Expressions: Algebraic Laws & Applications

Conversion of Regular Expression to Finite Automata (FA)

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 Expression

Outline:
- Equivalence of Regular Expressions and Finite Automata (FA)
- Kleens Theorem
- Conversion of Finite Automata (FA) to Regular Expression

Pumping Lemma and Closure Properties of Regular Languages

Pumping Lemma for Regular Sets / Regular Languages

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 Languages

Outline:
- Closure Operation
- Closure Property
- Closure Properties for Regular Sets / Regular Languages
- Decision Properties for Regular Sets / Regular Languages
- Converting among Regular Expressions

Equivalence and Minimization of Finite Automatons (FAs)

Equivalence between two Finite State Machines (FSMs) / Finite Automatons (FAs)

Outline:
- FSM Equivalence
- FSM Equivalence Algorithm
- FSM Equivalence -Example Problems

Minimization of Deterministic Finite Automata (DFA)

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 DFA

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

Regular Grammars and Finite Automata (FA)

Introduction to Regular Grammars

Outline:
- Definition of Formal Grammar
- Left-linear and Right-linear grammars
- Regular Grammars
- Examples

Regular Grammars and Finite Automata (FA)

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

Context-Free Grammars

Introduction to Context-free Grammars (CFG's)

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 CFGs

Outline:
- Parse Tree or Derivation Tree
- Applications of CFGs: Parser and Markup Languages

Context free Grammars (CFG's): Ambiguity

Outline:
- Ambiguity in Grammars and Languages
- Ambiguous Grammar
- Example problems on ambiguous grammars

Context free Grammars (CFG's): Eliminating Ambiguity

Outline:
- Ambiguity in Grammars and Languages
- Ambiguous Grammar
- Eliminating Ambiguity in CFGs
- Example problems on ambiguous grammars

Push Down Automata

Introduction to Pushdown Automata (PDA)

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 Stack

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-1

Outline:
- Design of PDA for the given CFL
- Pushdown Automata (PDA)
- Context Free Language (CFL)
- Example problem-1

Design of PDA for CFL part-2

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 PDA

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 PDA

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)

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 Context- Free Grammars

Normal Forms for CFGs: Removing useless symbols & useless productions

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 Productions

Outline:
- Normal forms for CFGs
- Removing Null productions
- Removing Unit productions
- Example problems

Normal forms for CFG: Chomsky Normal Form (CNF)

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)

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

Pumping Lemma and Closure Properties of Context-Free Languages

Pumping Lemma for Context-Free Languages

Outline:
- Statement of pumping lemma
- Applications
- Example problems

Closure Properties of Context-Free Languages

Outline:
- Closure properties of CFL’s
- Decision properties of CFL‘s
- Membership Algorithm for CFG: CYK Algorithm
- Undecidable CFL Problems
- Applications of CFL’

Turing Machine (TM)

Introduction to Turing Machine (TM)

Outline:
- Introduction to Turing Machine
- Formal Description • Instantaneous Description (ID)
- The Language of a Turing Machine
- Acceptance of Languages by TM

Closure properties of Recursive and Recursively Enumerable Languages

Outline:
- The Language of a Turing Machine
- Acceptance of Languages by TM
- Recursively Enumerable Language (REL)
- Recursive Language
- Closure properties of Recursive and Recursively Enumerable Languages

Design of Turing Machine for Languages

Outline:
- Introduction to Turing Machine
- Formal Description
- Instantaneous Description (ID)
- The Language of a Turing Machine
- Acceptance of Languages by TM
- Design of TM for Languages
- Example Problems

Types of Turing Machine (TM)

Outline:
- Various types of Turing Machines
- Church’s hypothesis
- Counter Machines (or) Offline Turing Machines
- Composite and Iterated Turing Machines
- Turing Machines and Halting

Turing Machine (TM)- Computable Functions

Outline:
- Computable Functions
- Construction of Turing Machine for Computable Functions
- Example Problems

Undecidability

Undecidability-Recursively Enumerable Language and Turing Machine

Outline:
- Undecidability - Introduction
- A Language that is Not Recursively Enumerable
- An Undecidable Problem That is RE
- Recursive Languages
- Properties of Recursive Languages
- Undecidable Problems about Turing Machines

Undecidability-Post's Correspondence Problem (PCP) & Other Undecidable Problems

Outline:
- Post's Correspondence Problem (PCP)
- Modified Post Correspondence Problem (MPCP)
- Other Undecidable Problems
- Type-0 Grammar: Phrase Structured or Unrestricted Grammar
- Type-1 Language: Context-Sensitive Language (CSL)
- Type-1 Grammar: Context-Sensitive Grammar (CSG)
- Type-1 Acceptor: Liner Bounded Automata (LBA)

Chomsky Hierarchy of Formal Languages and Recognizers

Outline:
- Classification of Formal Languages and Recognizers/Acceptors
- Type-0 Language: Recursively Enumerable Language (REL)
- Type-0 Grammar: Phrase Structured or Unrestricted Grammar
- Type-0 Acceptor: Turing Machine (TM)
- Type-1 Language: Context-Sensitive Language (CSL)
- Type-1 Grammar: Context-Sensitive Grammar (CSG)
- Type-1 Acceptor: Liner Bounded Automata (LBA)
- Type-2 Language: Context-Free Language (CFL)
- Type-2 Grammar: Context-Free Grammar (CFG)
- Type-2 Acceptor: Pushdown Automata (PDA)
- Type-3 Language: Regular Language
- Type-3 Grammar: Regular Grammar
- Type-3 Acceptor: Finite Automata (FA)

Solved Example Problems

Conversion of Regular Expression to Finite Automata-Example problem

Construction of Finite Automata that accepts atleast two consecutive 0's or 1's

Construction of Finite Automata (FA) that accepts at least two consecutive 0's or 1's

Construction of DFA that accepts Odd number of 0's and 1's

Construction of DFA that accepts Odd number of 0's and 1's

Practice Test

Practice Test

Popular Searches

Formal Languages and Automata Theory

Online

₹ 449 2299

Quick Facts

Course overview

The highlights

Program offerings

Course and certificate fees

Fees information

certificate availability

certificate providing authority

Who it is for

What you will learn

The syllabus

Introduction to Finite Automata

Introduction to Automata Theory

Fundamental Concepts of Automata Theory and Chomsky Hierarchy

Introduction to Finite Automata (FA)

Finite Automata (FA): Acceptance, Structural Representations and Complexity

Deterministic Finite Automata (DFA)

Nondeterministic Finite Automata (NFA)

Equivalence of NFA and DFA

Finite Automata with Epsilon Transitions

Finite Automata with Epsilon Transitions

Equivalence of NFA with and without Epsilon Moves (Eliminating Epsilon Transitions)

Conversion of NFA Epsilon (with epsilon) to DFA

Finite Automata with Output: Moore and Mealy Machines

Introduction to Moore and Mealy machines

Conversion of Mealy machine to Moore machine

Conversion of Moore machine to Mealy machine

Regular Expressions and Regular Languages

Introduction to Regular Expressions

Regular Expressions: Algebraic Laws & Applications

Conversion of Regular Expression to Finite Automata (FA)

Conversion of Finite Automata (FA) to Regular Expression

Pumping Lemma and Closure Properties of Regular Languages

Pumping Lemma for Regular Sets / Regular Languages

Closure Properties & Decision Properties for Regular Sets / Regular Languages

Equivalence and Minimization of Finite Automatons (FAs)

Equivalence between two Finite State Machines (FSMs) / Finite Automatons (FAs)

Minimization of Deterministic Finite Automata (DFA)

Construction of Minimized DFA

Regular Grammars and Finite Automata (FA)

Introduction to Regular Grammars

Regular Grammars and Finite Automata (FA)

Context-Free Grammars

Introduction to Context-free Grammars (CFG's)

Context-free Grammars (CFG's): Parse Tree/Derivation Tree & Applications of CFGs

Context free Grammars (CFG's): Ambiguity

Context free Grammars (CFG's): Eliminating Ambiguity

Push Down Automata

Introduction to Pushdown Automata (PDA)

Pushdown Automata (PDA)-Acceptance of Languages by Final State & Empty Stack

Design of PDA for CFL part-1

Design of PDA for CFL part-2

Equivalence of PDA's and CFG's: Conversion of CFG to PDA

Equivalence of PDA's and CFG's: Conversion of CFG to PDA

Deterministic Pushdown Automata (DPDA)

Normal Forms for Context- Free Grammars

Normal Forms for CFGs: Removing useless symbols & useless productions

Normal forms for CFG: Removing Null Productions & Unit Productions

Normal forms for CFG: Chomsky Normal Form (CNF)

Normal Forms for CFG- Greibach Normal Form (GNF)

Pumping Lemma and Closure Properties of Context-Free Languages

Pumping Lemma for Context-Free Languages

Closure Properties of Context-Free Languages

Turing Machine (TM)

Introduction to Turing Machine (TM)

Closure properties of Recursive and Recursively Enumerable Languages

Design of Turing Machine for Languages

Types of Turing Machine (TM)

Turing Machine (TM)- Computable Functions

Undecidability

Undecidability-Recursively Enumerable Language and Turing Machine

Undecidability-Post's Correspondence Problem (PCP) & Other Undecidable Problems

Chomsky Hierarchy of Formal Languages and Recognizers

Solved Example Problems

Conversion of Regular Expression to Finite Automata-Example problem

Construction of Finite Automata that accepts atleast two consecutive 0's or 1's