book

Introduction to Automata Theory, Formal Languages and Computation

Name: Introduction to Automata Theory, Formal Languages and Computation
Author: Shyamalendu Kandar
ISBN: 9789332516335

by Shyamalendu Kandar

January 2013

Beginner to intermediate

650 pages

16h 11m

English

Pearson India

Read now

Unlock full access

Cover
Title Page
Contents
About the Author
Dedication
Foreword
Preface
Chapter 1: Basic Terminology
Introduction1.1 Basics of String1.2 Basics of Set Theory1.2.1 Subset1.2.2 Finite and Infinite Set1.2.3 Equal1.2.4 Algebraic Operations on Sets1.2.5 Properties Related to Basic Operation1.3 Relation on Set1.4 Graph and Tree1.4.1 Graph1.4.2 Incident and Degree of a Vertex1.4.3 Isolated Vertex, Pendant Vertex1.4.4 Walk1.4.5 Path and Circuit1.4.6 Connected and Disconnected Graph1.4.7 Tree1.5 Basics of Digital Electronics1.6 Digital Circuit1.7 Basics of Automata Theory and Theory of Computation1.8 History of Automata Theory1.9 Use of AutomataWhat We Have Learned So FarSolved ProblemsFill in the BlanksExercise
Chapter 2: Language and Grammar
Introduction2.1 Grammar2.2 The Chomsky HierarchyWhat We Have Learned So FarSolved ProblemsMultiple Choice QuestionsGATE QuestionsFill in the BlanksExercise
Chapter 3: Finite Automata
Introduction3.1 History of the Automata Theory3.2 Use of Automata3.3 Characteristics of Automaton3.3.1 Characteristics3.4 Finite Automata3.5 Graphical and Tabular Representation FA3.6 Transitional System3.6.1 Acceptance of a String by Finite Automata3.7 DFA and NFA3.8 Conversion of an NFA to a DFA3.8.1 Process of Converting an NFA to a DFA3.9 NFA with ∈(null) Move3.9.1 Usefulness of NFA with ∈ Move3.9.2 Conversion of an NFA with ∈ Moves to DFA without ∈ Move3.10 Equivalence of DFA and NFA3.11 Dead State3.12 Finite Automata with Output3.12.1 The Mealy Machine3.12.2 The Moore Machine3.12.3 Tabular and Transitional Representation of the Mealy and Moore Machines3.13 Conversion of One Machine to Another3.13.1 Tabular Format3.13.2 Transitional Format3.14 Minimization of Finite Automata3.14.1 Process of Minimizing3.15 Myhill–Nerode Theorem3.15.1 Equivalence Relation3.15.2 Statement of the Myhill–Nerode Theorem3.15.3 Myhill–Nerode Theorem in Minimizing a DFA3.16 Two-way Finite Automata3.17 Application of Finite Automata3.18 Limitations of Finite AutomataWhat We Have Learned So FarSolved ProblemsMultiple Choice QuestionsGATE QuestionsFill in the BlanksExercise

Chapter 4: Finite State Machine
Introduction4.1 Sequence Detector4.2 Binary Counter4.2.1 Designing Using Flip Flop (T Flip Flop and SR Flip Flop)4.3 Finite State Machine4.3.1 Capabilities and Limitations of Finite-State Machine4.4 State Equivalence and Minimization of Machine4.5 Incompletely Specified Machine, Minimal Machine4.5.1 Simplification4.6 Merger Graph4.7 Compatibility Graph and Minimal Machine Construction4.7.1 Compatible Pair4.7.2 Implied Pair4.7.3 Compatibility Graph4.7.4 Minimal Machine Construction4.7.5 Minimal Machine4.8 Merger Table4.8.1 Construction of a Merger Table4.9 Finite Memory and Definite Memory Machine4.9.1 Finite Memory Machine4.9.2 Constructing the Method of Connection Matrix4.9.3 Vanishing of Connection Matrix4.9.4 Definite Memory machine4.10 Information Lossless Machine4.10.1 Test for Information Losslessness
4.11 Inverse Machine
4.12 Minimal Inverse MachineWhat We Have Learned So FarSolved ProblemsMultiple Choice QuestionsFill in the BlanksExercise
Chapter 5: Regular Expression
Introduction5.1 Basics of Regular Expression5.1.1 Some Formal Recursive Definitions of RE5.2 Basic Operations on Regular Expression5.2.1 Kleene’s Closure5.3 Identities of Regular Expression5.4 The Arden’s Theorem5.4.1 Process of Constructing Regular Expression from Finite Automata5.5 Construction of Finite Automata from a Regular Expression5.5.1 Conversion of an RE to NFA with ∈ transition5.5.2 Direct Conversion of RE to DFA5.6 NFA with ∈ Move and Conversion to DFA by ∈ -Closure Method5.6.1 Conversion of an NFA with ∈ move to a DFA5.7 Equivalence of Two Finite Automata5.8 Equivalence of Two Regular Expressions5.9 Construction of Regular Grammar from an RE5.10 Constructing FA from Regular Grammar5.11 Pumping Lemma for Regular Expression5.12 Closure Properties of Regular Set5.13 Decision Problems of Regular Expression5.14 ‘Grep’ and Regular Expression5.15 Application of Regular ExpressionWhat We Have Learned So FarSolved ProblemsMultiple Choice QuestionsGATE QuestionsFill in the BlanksExercise
Chapter 6: Context-free Grammar
Introduction6.1 Definition of Context-free Grammar6.1.1 Backus Naur Form (BNF)6.2 Derivation and Parse Tree6.2.1 Derivation6.2.2 Parse Tree6.3 Ambiguity in Context-free Grammar6.4 Left Recursion and Left Factoring6.4.1 Left Recursion6.4.2 Left Factoring6.5 Simplification of Context-free Grammar6.5.1 Removal of Useless Symbols6.5.2 Removal of Unit Productions6.5.3 Removal of Null Productions6.6 Linear Grammar6.6.1 Right Linear to Left Linear6.6.2 Left Linear to Right Linear6.7 Normal Form6.7.1 Chomsky Normal Form6.7.2 Greibach Normal Form6.8 Closure Properties of Context-free Language6.8.1 Closed Under Union6.8.2 Closed Under Concatenation6.8.3 Closed Under Star Closure6.8.4 Closed Under Intersection6.8.5 Not Closed Under Complementation6.8.6 Every Regular Language is a Context-free Language6.9 Pumping Lemma for CFL6.10 Ogden’s Lemma for CFL6.11 Decision Problems Related to CFG6.11.1 Emptiness6.11.2 Finiteness6.11.3 Membership Problem6.12 CFG and Regular Language6.13 Applications of Context-free GrammarWhat We Have Learned So FarSolved ProblemsMultiple Choice QuestionsGATE QuestionsFill in the BlanksExercise
Chapter 7: Pushdown Automata
Introduction7.1 Basics of PDA7.1.1 Definition7.1.2 Mechanical Diagram of the PDA7.2 Acceptance by a PDA7.2.1 Accepted by an Empty Stack (Store)7.2.2 Accepted by the Final State7.3 DPDA and NPDA7.3.1 Deterministic Pushdown Automata (DPDA)7.3.2 Non-deterministic Pushdown Automata (NPDA)7.4 Construction of PDA from CFG7.5 Construction of CFG Equivalent to PDA7.6 Graphical Notation for PDA7.7 Two-stack PDAWhat We Have Learned So FarSolved ProblemsMultiple Choice QuestionsGATE QuestionsFill in the BlanksExercise
Chapter 8: Turing Machine
Introduction8.1 Basics of Turing Machine8.1.1 Mechanical Diagram8.1.2 Instantaneous Description (ID) in Respect of TM8.2 Transitional Representation of Turing Machine8.3 Non-deterministic Turing Machine8.4 Conversion of Regular Expression to Turing Machine8.5 Two-stack PDA and Turing Machine8.5.1 Minsky TheoremWhat We Have Learned So FarSolved ProblemsMultiple Choice QuestionsGATE QuestionsFill in the BlanksExercise
Chapter 9: Variations of the Turing Machine
Introduction9.1 Variations of the Turing Machine9.1.1 Multi-tape Turing Machine9.1.2 Multi-head Turing Machine9.1.3 Two-way Infinite Tape9.1.4 K-dimensional Turing Machine9.1.5 Non-deterministic Turing Machine9.1.6 Enumerator9.2 Turing Machine as an Integer Function9.3 Universal Turing Machine9.4 Linear-Bounded Automata (LBA)9.5 Post Machine9.6 Church’s ThesisWhat We Have Learned So FarSolved ProblemsMultiple Choice QuestionsGATE QuestionsExercise
Chapter 10: Computability and Undecidability
Introduction10.1 TM Languages10.1.1 Turing Acceptable10.1.2 Turing Decidable10.2 Unrestricted Grammar10.2.1 Turing Machine to Unrestricted Grammar10.2.2 Kuroda Normal Form10.2.3 Conversion of a Grammar into the Kuroda Normal Form10.3 Modified Chomsky Hierarchy10.4 Properties of Recursive and Recursively Enumerable Language10.5 Undecidability10.6 Reducibility10.7 Post’s Correspondence Problem (PCP)10.8 Modified Post Correspondence Problem10.8.1 Reduction of MPCP to PCPWhat We Have Learned So FarSolved ProblemsMultiple Choice QuestionsGATE QuestionsExercise
Chapter 11: Recursive Function
Introduction11.1 Function11.1.1 Different Types of Functions11.2 Initial Functions11.3 Recursive Function11.4 Gödel Number11.4.1 Russell’s Paradox11.5 Ackermann’s Function11.6 Minimalization11.7 μ Recursive11.7.1 Properties of a μ Recursive Function11.8 λ Calculus11.9 Cantor Diagonal Method11.10 The Rice TheoremWhat We Have Learned So FarSolved ProblemsMultiple Choice QuestionsExercise
Chapter 12: Computational Complexity
Introduction12.1 Types of Computational Complexity12.1.1 Time Complexity12.1.2 Space Complexity12.2 Different Notations for Time Complexity12.2.1 Big Oh Notation12.2.2 Big Omega (Ω) Notation12.2.3 Theta Notation (Θ)12.2.4 Little-oh Notation (o)12.2.5 Little Omega Notation (ω)12.3 Problems and Its Classification12.4 Different Types of Time Complexity12.4.1 Constant Time Complexity12.4.2 Logarithmic Time Complexity12.4.3 Linear Time Complexity12.4.4 Quasilinear Time Complexity12.4.5 Average Case Time Complexity12.4.6 Polynomial Time Complexity12.4.7 Super Polynomial Time Complexity12.5 The Classes P12.6 Non-polynomial Time Complexity12.7 Polynomial Time Reducibility12.8 Deterministic and Non-deterministic Algorithm12.8.1 Tractable and Intractable Problem12.9 P = NP?—The Million Dollar Question12.10 SAT and CSAT Problem12.10.1 Satisfiability Problem (SAT)12.10.2 Circuit Satisfiability Problem (CSAT)12.11 NP Complete12.11.1 Cook–Levin Theorem12.12 NP Hard12.12.1 Properties of NP Hard Problems12.13 Space ComplexityWhat We Have Learned So FarSolved ProblemsMultiple Choice QuestionsGATE QuestionsExercise
Chapter 13: Basics of Compiler Design
Introduction13.1 Definition13.2 Types of Compiler13.2.1 Difference Between Single Pass and Multi Pass Compiler13.3 Major Parts of Compiler13.3.1 Lexical Analysis13.3.2 Syntax Analysis13.3.3 ParserWhat We Have Learned So FarMultiple Choice QuestionsGATE QuestionsExercise
Chapter 14: Advance Topics Related to Automata
Introduction14.1 Matrix Grammar14.2 Probabilistic Finite Automata14.2.1 String Accepted by a PA14.3 Cellular Automata14.3.1 Characteristics of Cellular Automata14.3.2 Applications of Cellular Automata
References
Acknowledgements
Copyright
Back Cover

Content preview from Introduction to Automata Theory, Formal Languages and Computation

1.2 Basics of Set Theory

1.2.1 Subset

1.2.2 Finite and Infinite Set

1.2.3 Equal

1.2.4 Algebraic Operations on Sets

1.2.5 Properties Related to Basic Operation

1.3 Relation on Set

1.4 Graph and Tree

1.4.1 Graph

1.4.2 Incident and Degree of a Vertex

1.4.3 Isolated Vertex, Pendant Vertex

1.4.4 Walk

1.4.5 Path and Circuit

1.4.6 Connected and Disconnected Graph

1.4.7 Tree

1.5 Basics of Digital Electronics

1.6 Digital Circuit

1.7 Basics of Automata Theory and Theory of Computation

1.8 History of Automata Theory

1.9 Use of Automata

What We Have Learned So Far

Solved Problems

Fill in the Blanks

Exercise

2. Language and Grammar

Introduction ...

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.

Read now

Unlock full access

More than 5,000 organizations count on O’Reilly

O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.

Julian F.

Head of Cybersecurity

I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.

Addison B.

Field Engineer

I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.

Amir M.

Data Platform Tech Lead

I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.

Mark W.

Embedded Software Engineer

Introduction to Formal Languages, Automata Theory and Computation

Publisher Resources

ISBN: 9788131793510

Cloud Computing

Data Engineering

Data Science

AI & ML

Programming Languages

Software Architecture

IT/Ops

Security

Design

Business

Soft Skills

Introduction to Automata Theory, Formal Languages and Computation

by Shyamalendu Kandar

Contents

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.