Discrete Structure and Automata Theory for Learners: Learn Discrete Structure Concepts and Automata Theory with JFLAP

by Dr. Umesh Sehgal, Ms. Sukhpreet Kaur Gill

Length: 368 pages
Edition: 1
Language: English
Publisher: BPB Publications
Publication Date: 2020-09-05
ISBN-10: 9389845386
ISBN-13: 9789389845389
Sales Rank: #6036956 (See Top 100 Books)

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.

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