## Contents

*1.2.4 Algebraic Operations on Sets*

*1.2.5 Properties Related to Basic Operation*

*1.4.2 Incident and Degree of a Vertex*

*1.4.3 Isolated Vertex, Pendant Vertex*

*1.4.6 Connected and Disconnected Graph*

1.5 Basics of Digital Electronics

1.7 Basics of Automata Theory and Theory of Computation

1.8 History of Automata Theory

3.1 History of the Automata Theory

3.3 Characteristics of Automaton

3.5 Graphical and Tabular Representation FA

*3.6.1 Acceptance of a String by Finite Automata*

3.8 Conversion of an NFA to a DFA

*3.8.1 Process of Converting an NFA to a DFA*

*3.9.1 Usefulness of NFA with *∈* Move*

*3.9.2 Conversion of an NFA with *∈* Moves to DFA without *∈* Move*

3.10 Equivalence of DFA and NFA

3.12 Finite Automata with Output

*3.12.3 Tabular and Transitional Representation of the Mealy and Moore Machines*

3.13 Conversion of One Machine to Another

3.14 Minimization of Finite Automata

*3.15.2 Statement of the Myhill–Nerode Theorem*

*3.15.3 Myhill–Nerode Theorem in Minimizing a DFA*

3.17 Application of Finite Automata

3.18 Limitations of Finite Automata

*4.2.1 Designing Using Flip Flop (T Flip Flop and SR Flip Flop)*

*4.3.1 Capabilities and Limitations of Finite-State Machine*

4.4 State Equivalence and Minimization of Machine

4.5 Incompletely Specified Machine, Minimal Machine

*4.7 Compatibility Graph and Minimal Machine Construction*

*4.7.4 Minimal Machine Construction*

*4.8.1 Construction of a Merger Table*

4.9 Finite Memory and Definite Memory Machine

*4.9.2 Constructing the Method of Connection Matrix*

*4.9.3 Vanishing of Connection Matrix*

4.10 Information Lossless Machine

*4.10.1 Test for Information Losslessness*

5.1 Basics of Regular Expression

*5.1.1 Some Formal Recursive Definitions of RE*

5.2 Basic Operations on Regular Expression

5.3 Identities of Regular Expression

*5.4.1 Process of Constructing Regular Expression from Finite Automata*

5.5 Construction of Finite Automata from a Regular Expression

*5.5.1 Conversion of an RE to NFA with *∈* transition*

*5.5.2 Direct Conversion of RE to DFA*

5.6 NFA with ∈ Move and Conversion to DFA by ∈ -Closure Method

*5.6.1 Conversion of an NFA with * ∈* move to a DFA*

5.7 Equivalence of Two Finite Automata

5.8 Equivalence of Two Regular Expressions

5.9 Construction of Regular Grammar from an RE

5.10 Constructing FA from Regular Grammar

5.11 Pumping Lemma for Regular Expression

5.12 Closure Properties of Regular Set

5.13 Decision Problems of Regular Expression

5.14 ‘Grep’ and Regular Expression

5.15 Application of Regular Expression

6.1 Definition of Context-free Grammar

6.3 Ambiguity in Context-free Grammar

6.4 Left Recursion and Left Factoring

6.5 Simplification of Context-free Grammar

*6.5.1 Removal of Useless Symbols*

*6.5.2 Removal of Unit Productions*

*6.5.3 Removal of Null Productions*

*6.6.1 Right Linear to Left Linear*

*6.6.2 Left Linear to Right Linear*

6.8 Closure Properties of Context-free Language

*6.8.2 Closed Under Concatenation*

*6.8.3 Closed Under Star Closure*

*6.8.4 Closed Under Intersection*

*6.8.5 Not Closed Under Complementation*

*6.8.6 Every Regular Language is a Context-free Language*

6.11 Decision Problems Related to CFG

6.13 Applications of Context-free Grammar

*7.1.2 Mechanical Diagram of the PDA*

*7.2.1 Accepted by an Empty Stack (Store)*

*7.2.2 Accepted by the Final State*

*7.3.1 Deterministic Pushdown Automata (DPDA)*

*7.3.2 Non-deterministic Pushdown Automata (NPDA)*

7.4 Construction of PDA from CFG

7.5 Construction of CFG Equivalent to PDA

7.6 Graphical Notation for PDA

*8.1.2 Instantaneous Description (ID) in Respect of TM*

8.2 Transitional Representation of Turing Machine

8.3 Non-deterministic Turing Machine

8.4 Conversion of Regular Expression to Turing Machine

8.5 Two-stack PDA and Turing Machine

9. Variations of the Turing Machine

9.1 Variations of the Turing Machine

*9.1.1 Multi-tape Turing Machine*

*9.1.2 Multi-head Turing Machine*

*9.1.4 K-dimensional Turing Machine*

*9.1.5 Non-deterministic Turing Machine*

9.2 Turing Machine as an Integer Function

9.4 Linear-Bounded Automata (LBA)

10. Computability and Undecidability

*10.2.1 Turing Machine to Unrestricted Grammar*

*10.2.3 Conversion of a Grammar into the Kuroda Normal Form*

10.3 Modified Chomsky Hierarchy

10.4 Properties of Recursive and Recursively Enumerable Language

10.7 Post’s Correspondence Problem (PCP)

10.8 Modified Post Correspondence Problem

*10.8.1 Reduction of MPCP to PCP*

*11.1.1 Different Types of Functions*

*11.7.1 Properties of a μ Recursive Function*

12.1 Types of Computational Complexity

12.2 Different Notations for Time Complexity

*12.2.5 Little Omega Notation (*ω*)*

12.3 Problems and Its Classification

12.4 Different Types of Time Complexity

*12.4.1 Constant Time Complexity*

*12.4.2 Logarithmic Time Complexity*

*12.4.4 Quasilinear Time Complexity*

*12.4.5 Average Case Time Complexity*

*12.4.6 Polynomial Time Complexity*

*12.4.7 Super Polynomial Time Complexity*

12.6 Non-polynomial Time Complexity

12.7 Polynomial Time Reducibility

12.8 Deterministic and Non-deterministic Algorithm

*12.8.1 Tractable and Intractable Problem*

12.9 P = NP?—The Million Dollar Question

*12.10.1 Satisfiability Problem (SAT)*

*12.10.2 Circuit Satisfiability Problem (CSAT)*

*12.12.1 Properties of NP Hard Problems*

*13.2.1 Difference Between Single Pass and Multi Pass Compiler*

14. Advance Topics Related to Automata

14.2 Probabilistic Finite Automata

*14.2.1 String Accepted by a PA*

*14.3.1 Characteristics of Cellular Automata*