BPB Online LLP
Discrete Structure and Automata Theory for Learners
Discrete Structure and Automata Theory for Learners
US$ 19.95
The publisher has enabled DRM protection, which means that you need to use the BookFusion iOS, Android or Web app to read this eBook. This eBook cannot be used outside of the BookFusion platform.
Description
Contents
Reviews

Learn to identify the implementation of Discrete Structure and Theory of Automata in a myriad of applications used in day to day life

Key Features
Learn how to write an argument using logical notation and decide if the argument is valid or not valid.
Learn how to use the concept of different data structures (stacks, queues, sorting concept, etc.) in the computer science field.
Learn how to use Automata Machines like FSM, Pushdown automata, Turing machine, etc. in various applications related to computer science through suitable practical illustration.
Learn how to implement the finite state machine using JFLAP (Java Formal Languages and Automata Package).

Description
This book's purpose is to provide a modern and comprehensive introduction to the subject of Discrete Structures and Automata Theory. Discrete structures, also called Discrete Mathematics, are an exciting and active subject, particularly due to its extreme relevance to both Mathematics and Computer Science and Algorithms. This subject forms a common foundation for rigorous Mathematical, Logical Reasoning and Proofs, as well as a formal introduction to abstract objects that are essential tools in an assortment of applications and effective computer implementations. Computing skills are now an integral part of almost all the Scientific fields, and students are very enthusiastic about being able to harness the full computing power of these tools. Further, this book also deep dives into the Automata Theory with various examples that illustrate the basic concepts and is substantiated with multiple diagrams. The book's vital feature is that it contains the practical implementation of the Automata Machine example through the JFLAP Tool. Courses on Discrete Structures and Automata theory are offered at most universities and colleges.

What will you learn
Understand the basic concepts of Sets and operations in Sets.
Demonstrate different traversal techniques for Trees and Graphs.
Deep dive into the concept of Mathematical Induction, Sets, Relations, Functions, Recursion, Graphs, Trees, Boolean Algebra, and Proof techniques.
Understand the concept of Automata Machines in day to day life like the Elevator, Turnstile, Genetic Algorithms, Traffic lights, etc.
Use the JFLAP tool to solve the various exercise problems related to automata theory.

Who this book is for
This book is a must-read to everyone interested in improving their concepts regarding Discrete Structure and Automata Theory.
Table of Contents
1. Set Theory
2. Relations and Functions
3. Graph Theory
4. Trees
5. Algebraic Structure
6. Recursion and Recurrence Relations
7. Sorting
8. Queues
9. Introduction
10. Finite Automata Theory
11. Theory of Machines
12. Regular Language
13. Grammar
14. Pushdown Automata
15. Cellular Automata
16. Turning Machine
17. Problems Solving Using JFLAP Tool
18. Revision Questions

About The Authors
Dr. UMESH SEHGAL completed his Ph.D.,M.Phil. Computer Science and MCA. He held academic positions at the GNA University as an A.P in FCS Department. He has achieved the Best Educationist Award in 2017.He has achieved the Indira Gandhi Education Excellence Award in 2017.He has achieved the Best Researcher Award in 2018-19.

SUKHPREET KAUR GILL received the M.Tech. degree in Computer Science and Engineering from Guru Nanak Dev Engineering College, Ludhiana. She is currently working as Assistant Professor at GNA University Phagwara. She has achieved the Bright Educator Award 2019. She has published several articles in leading International and National Computer science journals.

Language
English
ISBN
9789389845389
Cover Page
Title Page
Copyright Page
Dedication Page
About the Authors
About the Reviewer
Preface
Errata
Table of Contents
SECTION A: UNIT-1
1. Set Theory
Structure
Objectives
What is discrete mathematics?
Why discrete mathematics?
Introduction to problem-solving
A framework for problem-solving
Understanding the issue of problem
Making a plan to make a solution
Example 1:
Introduction of sets
Definition (equality of sets)
Definition (subset)
Definition (cardinality)
Definition (empty set)
Definition (universal set)
Definition (power set)
Exercise-based on topics covered
Definition (union)
Definition (intersection)
Definition (difference)
Definition (complement)
Definition (ordered pair)
Definition (cartesian product)
Definition (ordered n-tuple)
Definition (cartesian product)
Definition (equality of n-tuples)
Exercise
Power sets
Counting principles
Exercise
2. Relations and Functions
Structure
Objectives
Introduction
Types of relations
Definition (ordered pair)
Definition (equality of ordered pairs)
Definition (binary relation)
Definition (cartesian product)
Definition (ordered n-tuple)
Definition (cartesian product)
Definition (equality of n-tuples)
Definition (n-ary relation)
Special relations
Definition (equality of binary relation)
Definition (equality of n-ary relation)
Closure properties
Equivalence relations
Partial ordering relations
Relation functions
Definition (function)
Definition (sum and product)
Definition (one-to-one)
Definition (onto)
Definition (bisection)
Definition (Inverse)
Definition (composite function)
BIG - OH
Definition (big-oh)
Growth of combinations of functions
Definition (max function)
BIG - OMEGA AND BIG - THETA
Definition (big-omega)
Definition (big-theta)
Little - Oh and Little - Omega
Exercise
3. Graph Theory
Structure
Objectives
Introduction of graph theory
Basic terms of graph theory
Handshaking Lemma
Graphs and multigraph
Multi graphs
Isomorphic graphs
Shortest path in waited graphs
Eulerian and Hamiltonian paths
Hamiltonian graphs
Konigsberg bridge
Euler’s solution
Additional fun with graphs
A different problem with the same solution
Graph theory today
Bipartite graphs
Planner graphs
Graph coloring
Exact algorithms
Graph traversal techniques
Exercise
4. Trees
Structure
Objectives
Introduction
Plane tree
Labeled trees
Unlabeled trees
Exercise
Types of trees
Binary trees
Binary tree traversal
Stacks and queues
Adding to stack
Deletion in stack
Addition to queue
Deletion in queue
Linked lists (in spanning tree functions)
Complete trees
Exercise
SECTION A: UNIT-2
5. Algebraic Structure
Structure
Objectives
Introduction
One set with operations
Simple structures
Group-like structures
Ring-like structures or Ringoids
Lattice structures
Arithmetic’s
Algebra-like structures
Universal algebra
Abstract algebra
Modern algebra
Exercise
6. Recursion and Recurrence Relations
Structure
Objectives
Introduction
Formal definitions of recursion
Informal definition
Recursion in Mathematics
Functional recursion
Recursion in Computer Science
The recursion theorem
Recurrence relation
Fibonacci numbers
Linear homogeneous
Rational generating functions
Relationship to difference equations narrowly
General methods (problem-solving)
Solving via linear algebra
Solving with Z-transform
Solving non-homogeneous recurrence relations
Digital signal processing
Exercise
7. Sorting
Structure
Objectives
Introduction
Sorting algorithms
Bubble sort
Analysis of bubble sort
Insertion sort
Heap sort
Animation
Quick sort
Merge sort
Bin sort
Constraints on bin sort
Heap sort algorithm implementation
Radix sorting
Exercise
8. Queues
Structure
Objectives
Introduction of queues
Performance
Priority queues
Stacks
Heaps
Exercise
SECTION B: UNIT-3
9. Introduction
Structure
Objectives
Concepts of automata
Computation
Formal definition
Input symbols
Automata states
Accepting strings
Recognized language
Applications of automata theory
Linguistics
Regular expressions example
Grammar example
Biology
Basic definitions
Automata theory
Finite state machine
DF A: Deterministic finite automata
NDF A: Nondeterministic finite automata
Exercise
10. Finite Automata Theory
Structure
Objectives
Finite automata
Uses of finite automata
The notation
DFA (Deterministic finite automata)
DFA: Informal definition
Informal definition
Non-deterministic finite automata (NFA)
Informal introduction
Formal definition
States of finite automata
Limitation of FA
Transition function
Direct (Represented by δ)
Indirect (Represented by δ’)
NFA runs
Subset construction
Closure properties
Equivalence of DFA and NDFA With ε-moves
Informal introduction
Formal definition
Equivalence to NFA and DFA
Closure properties
Difference between DFA and NDFA
Exercise
11. Theory Of Machines
Structure
Objectives
Introduction
Some examples
States
Transitions
Events
Actions
The execution model
Designing state machines
Finite state machine
N-word FSM
State/event table
Unified modeling language (UML) state machines
SDL state machines
Recognizers and acceptors
Sequences relating to FSMs
Transducers
Mealy machines
Moore machine
Mealy to Moore and Moore to Mealy machine transformation
Generators
Optimization
Software applications
Properties and limitations of FSM
Limitations of finite state machines
Exercise
SECTION B: UNIT-4
12. Regular Language
Structure
Objectives
Introduction
Formal definition
Regular expressions and sets
Examples
Equivalence to other formalisms
Closure properties
Deciding whether a language is regular
Complexity results
Subclasses
Regular sets and expressions
The Pumping Lemma for regular sets
Pumping Lemma
Pumping Lemma (Strong)
Closure properties
Closure properties of regular languages
Closure under union
Closure under concatenation and Kleene closure
Closure under intersection
Homomorphism
Closure under homomorphism
Inverse homomorphism’s
Closure proof for inverse homomorphism
Conclusion
Exercise
13. Grammar
Structure
Objectives
Introduction
Grammars
Formal definition
The syntax of grammars
The semantics of grammars
Context-free grammars
Regular grammars
Forms of generative grammar
Analytic grammars
Context-free and context-sensitive grammar
A grammar generator
Formal definition
Normal forms
Computational properties and uses
Context-free grammar
Derivation and parse tree
Left recursion
Simplification of CFG
Normal form
Construction FA
Chomsky normal form
Converting a grammar to Chomsky Normal Form
Transforming a Grammar to CNF
Greibach Normal Form
Exercise
SECTION B: UNIT-5
14. Pushdown Automata
Structure
Objectives
Pushdown automata
Application of pushdown machines
Unsolvable problems for pushdown automata
Exercise
15. Cellular Automata
Structure
Objectives
Introduction
Concept of cellular
The pattern used in automata
Classification
Reversible automata
Related automata
Evolving cellular automata using genetic algorithms
Formal language aspects
Exercise
16. Turing Machine
Structure
Objectives
Introduction
Deterministic and non-deterministic Turing machines
Equivalence with DTM’S
Types of Turing machines
Turing machines with two-dimensional tapes
Two-dimensional tapes
One-dimensional tape
Turing machines with multiple tapes
Turing machines with multiple heads
Turing machines with infinite tape
Non-deterministic Turing machines
Design of Turing machine
The halting problem of TM
Importance and consequences
PCP problem
Exercise
17. Problems Solving Using JFLAP Tool
Structure
Objectives
Java Formal Languages and Automata Package
Problem-solving with JFLAP
18. Revision Questions

Loading...