Discrete Structure and Automata Theory for Learners

Kaur Sehgal Dr. Umesh Gill Ms. Sukhpreet

Description

Learn to identify the implementation of Discrete Structure and Theory of Automata in a myriad of applications used in day to day lifeKey Featuresa- Learn how to write an argument using logical notation and decide if the argument is valid or not valid.a- Learn how to use the concept of different data structures (stacks, queues, sorting concept, etc.) in the computer science field.a- Learn how to use Automata Machines like FSM, Pushdown automata, Turing machine, etc. in various applications related to computer science through suitable practical illustration.a- Learn how to implement the finite state machine using JFLAP (Java Formal Languages and Automata Package).DescriptionThis 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 learna- Understand the basic concepts of Sets and operations in Sets.a- Demonstrate different traversal techniques for Trees and Graphs.a- Deep dive into the concept of Mathematical Induction, Sets, Relations, Functions, Recursion, Graphs, Trees, Boolean Algebra, and Proof techniques.a- Understand the concept of Automata Machines in day to day life like the Elevator, Turnstile, Genetic Algorithms, Traffic lights, etc.a- Use the JFLAP tool to solve the various exercise problems related to automata theory.Who this book is forThis book is a must-read to everyone interested in improving their concepts regarding Discrete Structure and Automata Theory.Table of Contents1. Set Theory2. Relations and Functions3. Graph Theory4. Trees5. Algebraic Structure6. Recursion and Recurrence Relations7. Sorting8. Queues9. Introduction10. Finite Automata Theory11. Theory of Machines12. Regular Language13. Grammar14. Pushdown Automata15. Cellular Automata16. Turning Machine17. Problems Solving Using JFLAP Tool18. Revision QuestionsAbout the AuthorsDr. 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.He has published several articles in leading International and National Computer science journals and has been an invited speaker at Wireless networks based lectures and conferences in the many universities and Institutes in India, Malaysia, China, and UAE.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.

Sujets

• Sciences et techniques
• Discrete mathematics
• Computer science

Informations

• Publié par: BPB Publications
• Date de parution: 05 septembre 2020
• Nombre de lectures: 0
• EAN13: 9789389845396
• Langue: English

Extrait

Discrete Structure and Automata Theory for Learners

Learn Discrete Structure Concepts and Automata Theory with JFLAP

Dr. Umesh Sehgal
Ms. Sukhpreet Kaur Gill
www.bpbonline.com
FIRST EDITION 2020
Copyright © BPB Publications, India
ISBN: 978-93-89845-38-9
All Rights Reserved. No part of this publication may be reproduced or distributed in any form or by any means or stored in a database or retrieval system, without the prior written permission of the publisher with the exception to the program listings which may be entered, stored and executed in a computer system, but they can not be reproduced by the means of publication.
LIMITS OF LIABILITY AND DISCLAIMER OF WARRANTY
The information contained in this book is true to correct and the best of author’s & publisher’s knowledge. The author has made every effort to ensure the accuracy of these publications, but cannot be held responsible for any loss or damage arising from any information in this book.
All trademarks referred to in the book are acknowledged as properties of their respective owners but BPB Publications cannot guarantee the accuracy of this information.
Distributors:
BPB PUBLICATIONS
20, Ansari Road, Darya Ganj
New Delhi-110002
Ph: 23254990/23254991
MICRO MEDIA
Shop No. 5, Mahendra Chambers,
150 DN Rd. Next to Capital Cinema,
V.T. (C.S.T.) Station, MUMBAI-400 001
Ph: 22078296/22078297
DECCAN AGENCIES
4-3-329, Bank Street,
Hyderabad-500195
Ph: 24756967/24756400
BPB BOOK CENTRE
376 Old Lajpat Rai Market,
Delhi-110006
Ph: 23861747
Published by Manish Jain for BPB Publications, 20 Ansari Road, Darya Ganj, New Delhi-110002 and Printed by him at Repro India Ltd, Mumbai
www.bpbonline.com
Dedicated to
Dedicated to my parents and my wife, Hardik the most precious gift of life has given to me.
— Dr. Umesh Sehgal
Dedicated to my parents
— Ms. Sukhpreet Kaur Gill
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. He has published several articles in leading International and National Computer science journals and has been an invited speaker at Wireless networks based lectures and conferences in the many universities and Institutes in India, Malaysia, China, and UAE. His research interests include areas of Cyber Security and Wireless Networks, Next Generation Network, Neural Networks, and he has taught many upper-level classes to Computer science students.
Dr. Umesh Sehgal (Assistant Professor)
Faculty of Computational Science, GNA University, Phagwara
Google Scholar: https://scholar.google.co.in/citations?user=z4Jd2r8AAAAJ&hl=en
Ms. 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. Her research interests include Natural Language Processing, deep learning, and Machine Learning.
Ms. Sukhpreet Kaur Gill (Assistant Professor)
Faculty of Computational Science, GNA University, Phagwara
Research Gate: https://www.researchgate.net/profile/Sukhpreet_Gill4
About the Reviewer
Dr. Gaurav Gupta , is currently serving as Assistant Professor at Punjabi University, Patiala (Pb), India after completing his Ph.D, M.Tech and B.Tech in Computer Science & Engineering from the University. He has more than 17 years of teaching experience and has supervised more than 45 M.Tech Dissertations. He is also supervising 4 Ph.D research scholars. He has contributed 89 articles in many reputed Journals besides participating in some international conferences. His research interests include Machine Learning, Data Science, Data Mining & Warehousing, Big Data, CRM, Information Systems, Knowledge Management, Cloud Computing and DIP. He is a member of UACEE, IAENG, IACSIT and SDIWC. He is on editorial board of various Journals.
Before joining Punjabi University, he served Chitkara University and RIMT University. He had delivered many Expert talks and headed workshops on Data Mining and its techniques in different colleges and universities. He also headed many committees at department level and university level.
Preface
The purpose of this book 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 to computer science and algorithms. The 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 scientific fields, and students are very enthusiastic about being able to harness the full computing power of these tools. Further, this book also deep dive into the automata theory with various examples that illustrate the basic concepts and is substantiated with various diagrams. While dealing with the concept of various theorems and algorithms, it basically focuses on constructions. Every construction is immediately followed by suitable illustrations. The vital feature of the book that it contains the practical implementation of Automata Machine example through the JFLAP Tool. Courses in discrete structures and Automata Theory are offered at most all universities and in an increasingly large portion of community colleges as well and are required by both math and computer science programs.
How the book evolved: Over the past many years this subjects course in Discrete structures and Automata theory and formal languages (to both mathematics and computer science majors) at many universities like GNAUniversity, GNDU, Lovely University, PTU, Punjabi University, Panjab University, Amity University, H.P University, Jaypee University, Manav Bharti University, Shoolini University, Himachal Pradesh Technical University, Hamipur,Shivaji University, Kolhapur, Pune University, Mumbai University, Sharda University, Noida International University, Jammu University, Sri Sai University, Career point University, etc. This standard curriculum is nonetheless important, and it should be included in any decent book or course on the subject. At the same time, it is also important to develop materials that reflect many of the advances and recent trends and applications of this area. Examples of some of the applications that are extensively treated in this book include simulation, genetic algorithms, network flows, probabilistic primality tests, public-key cryptography, and many applications to coding theory.
There have been numerous new developments in this vast subject, and the tasks that can be accomplished by students on their PCs are now very different than what was feasible even just 15 years ago. It is these exciting application areas that really make the topics of discrete structures so interesting and useful in applications, and is the reason that it is a required course for computer science students. Some of the topics covered in this book were introduced in various semesters in the author’s discrete structures classes, and others were further expounded upon in subsequent special topics classes. Examples include separate upper-level courses in each of the areas of graph theory and algorithms, simulation, genetic algorithms, and cryptography. Not being able to find books that included many of these new topics or had a good selection of exercises, the author found it necessary to prepare his own notes and exercise sets for many of these classes and topics. Starting about five years ago, with the aim of expanding his materials into a complete discrete structures textbook, the author began to prepare book materials and exercises for the core topics in discrete structures. Thus, the book has been evolving through classroom testing on a number of different courses first with the applications, and then with the core material.
A few comments about the numbering scheme are in order. All theoretical results theorems, lemmas, propositions, and corollaries are numbered sequentially in each chapter. Definitions, examples, labeled equations, figures, tables, algorithms, and exercises for the reader each have their own separate counters. The general index at the end of the book is preceded by separate indices for theoretical results and algorithms.
How technology is incorporated: Although the book highly encourages the use of computing platforms, it can still be used without any computers. The text proper is written for non-computer users, as are all of the ordinary exercises. As a general rule, technical comments and implementation suggestions for computer users are restricted to the computer exercise sets located at the end of most sections. The author divided a Book into two parts and three Sections. Section–A describes a Discrete structure in UNIT 1 and UNIT 2 (Chapter No. 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 ). and Section–B describe a Automata Theory and Formal Language in UNIT-3 , UNIT-4 , UNIT-5 (Chapter No. 9 , 10 , 11 , 12 , 13 , 14 , 15 , 16 , 17 , 18 ). The explanations of the algorithms and computer exercises are platform-independent. Algorithms are explained first in ordinary English, and when appropriate using a natural and easy-to-understand pseudo code that can be readily translated into any computer language Web page for the book is being maintained that includes, in particular, sample programs and programming notes