book

Formal Languages and Automata Theory

Name: Formal Languages and Automata Theory
Author: K.V.N. Sunitha
ISBN: 9789332558274

by K.V.N. Sunitha

April 2015

Intermediate to advanced

482 pages

11h 42m

English

Pearson Education India

Read now

Unlock full access

Cover
Title page
Brief Contents
Contents
Preface
Acknowledgements
List of Important Symbols
List of Important Abbreviations
About the Authors
1. Mathematical Preliminaries and Formal Languages
1.1 Set Theory1.1.1 Describing a Set1.1.2 Empty Set1.1.3 Identity and Cardinality1.1.4 Subset1.1.5 Power Sets1.1.6 Operations on Sets: Union, Intersection1.1.7 Set Theoretic Equalities1.1.8 Sequence versus Set1.1.9 Ordered Pairs1.1.10 Cartesian Product1.2 Relations1.2.1 Binary Relation1.2.2 Domain and Range of Relation1.2.3 Operations on Relations1.2.4 Properties of Relations1.3 Functions1.3.1 Definitions1.3.2 Types of Functions1.4 Alphabet, String and Language1.4.1 Operations on Language1.4.2 Grammars1.4.3 Types of Grammars–Chomsky Hierarchy1.5 Graphs and Trees1.5.1 Directed Graph1.5.2 Undirected Graph1.5.3 Trees1.6 Theorem Proving1.6.1 Proof by Induction1.6.2 Proof by Contradiction1.6.3 Proof by ExampleSummaryShort AnswersFill in the BlanksObjective Question BankExercises

2. Finite Automata
2.1 Finite-state Machine2.1.1 Finite-Automaton Model2.1.2 Properties of Transition Function ‘χ’2.1.3 Transition Diagram2.1.4 Transition Table2.2 Language Acceptance2.3 Two Types of Finite Automata2.3.1 Deterministic Finite Automata (DFA)2.3.2 Non-deterministic Finite Automaton (NFA)2.3.3 Acceptance of NFA2.4 Equivalence of DFAs and NFAs2.5 Converting NFA (MN) to DFA (MD)—Subset Construction2.6 NFA with Epsilon-(ε) Transitions2.6.1 Epsilon Closure (ε-closure)2.6.2 Eliminating ε-Transitions2.6.3 Converting NFA with ε-Transition to NFA without ε-Transition2.6.4 Converting NFA with ε-Transition to DFA2.7 Comparison Method for Testing Equivalence of Two FAs2.8 Reduction of Number of States in FA2.8.1 Indistinguishable States2.8.2 Equivalent Classes2.8.3 Minimization of DFA2.8.4 Minimization of DFA Using Myhill Nerode Theorem2.9 Finite Automata with Output2.9.1 Moore Machine2.9.2 Mealy Machine2.9.3 Equivalence Between Moore and Mealy Machines2.9.4 Interconversions Between Machines2.10 Applications of Finite Automata with Output2.10.1 The Full-adder2.10.2 The String Sequence DetectorSolved ProblemsSummaryShort AnswersFill in the BlanksObjective Question BankExercises
3. Regular Languages and Regular Grammars
3.1 Regular Expressions3.2 Regular Sets3.3 Identity Rules for Regular Expressions3.4 Algebraic Laws for Regular Expressions3.5 Equivalence of Finite Automata with Regular Expressions3.6 Constructing Regular Expression for Given DFA3.6.1 Arden’s Theorem3.6.2 Arden’s Theorem in Construction of RE3.6.3 Construction of RE Using Generalized NFA3.7 Pumping Lemma of Regular Expressions3.7.1 Formal Definition of the Pumping Lemma3.8 Regular Grammar3.8.1 Equivalence of Regular Grammar and Finite Automata3.8.2 Converting Finite Automaton to Regular Grammar3.9 Closure Properties of Regular Sets3.10 Applications of Regular Expressions3.10.1 Lexical Analysis3.10.2 Finding Patterns3.11 Decision Properties of Regular Languages3.11.1 Conversion from NFA to DFA3.11.2 Emptiness Membership and EquivalenceSolved ProblemsSummaryShort AnswersFill in the BlanksObjective Question BankExercises
4. Context Free Grammars and Context Free Languages
4.1 Context Free Grammars4.2 Derivation of CFGs4.3 Understanding the Language Defined by Grammars4.3.1 Leftmost and Rightmost Derivations4.3.2 Derivation Tree4.3.3 Equivalence of Parse Trees and Derivations4.4 Ambiguous Grammar4.4.1 Removing Ambiguity4.4.2 Inherent Ambiguity4.5 Simplification of Grammars4.5.1 Elimination of Useless Symbols4.5.2 Elimination of ε-Productions4.5.3 Eliminating Unit Productions4.6 Normal Forms4.6.1 The Chomsky Normal Form4.6.2 The Greibach Normal Form4.7 Pumping Lemma for CFL4.7.1 Lemma4.8 Decision Algorithms for CFLs4.8.1 Finiteness and Infiniteness4.9 Membership4.10 Closure Properties of CFLs4.11 Applications of CFGSolved ProblemsSummaryShort AnswersFill in the BlanksObjective Question BankExercises
5. Push Down Automata
5.1 Pushdown Automata5.1.1 Graphical Representation of PDA5.1.2 Instantaneous Description of PDA5.1.3 Language Acceptance by PDA5.2 Equivalence of Acceptance of Final State and Empty Stack5.3 Types of PDAs5.3.1 Deterministic PDA5.3.2 Closure Properties of DCFL5.3.3 Decision Properties of DCFLs5.3.4 DPDA and Regular Languages5.3.5 DPDA and Ambiguous Grammar5.4 Equivalence of PDA’s and CFG’s5.4.1 Constructing PDA for Given CFG5.4.2 Constructing CFG for the Given PDA5.5 Two-stack PDA5.6 Applications of PDA5.6.1 PDA as a Parser5.6.2 Top-down Parser Using the PDASolved ProblemsSummaryShort AnswersFill in the BlanksObjective Question BankExercises
6. Turing Machines
6.1 Turing Assumptions6.1.1 Instantaneous Description6.1.2 Turing Machine as Language Accepter6.2 Turing Machine as a Computational Machine6.3 Techniques for Turing Machine Construction6.3.1 Storage in Finite Control6.3.2 Multi-track Tape6.3.3 Checking off Symbols6.3.4 Subroutines6.3.5 Shifting Over6.4 Types of Turing Machines6.4.1 Non-deterministic Turing Machines6.4.2 Turing Machines with Two-dimensional Tapes6.4.3 Turing Machines with Multiple Tapes6.4.4 Turing Machines with Multiple Heads6.4.5 Turing Machines with Infinite Tape6.5 Church’s Thesis6.6 Turing Machines as Enumerators6.7 Universal Turing Machine6.8 Counter Machine6.9 Recursive and Recursively Enumerable Languages6.10 Linear Bound Automata and Context Sensitive Language6.10.1 Equivalence of LBA’s and CSG’sSolved ProblemsSummaryShort AnswersFill in the BlanksObjective Question BankExercises
7. Undecidability and Computability
7.1 Decision Problems7.2 Decidability and Decidable Languages7.2.1 Decidable Problems Concerning Regular Languages7.2.2 Decidable Problems Concerning Context Free Languages7.3 Halting Problem7.3.1 The Halting Problem for Turing Machines7.4 Diagonalization Method7.4.1 Undecidable Problems7.5 Post’s Correspondence Problem7.5.1 The Undecidability of Post’s Correspondence Problem7.5.2 Modified Version of PCP7.6 Reducibility7.6.1 Properties7.6.2 Mapping Reducibility7.6.3 Formal Definition of Mapping Reducibility7.7 Recursion Theorem7.7.1 Applications and Uses of Recursion7.8 Rice’s Theorem7.9 Ackermann’s FunctionSolved ProblemsSummaryShort AnswersFill in the BlanksObjective Question BankExercises
8. Non-deterministic Polynomial Completeness
8.1 NP-hard and NP-complete8.1.1 Classification of Problems8.2 P Problems8.3 NP Problems8.4 Tractable Problems8.5 NP-complete8.6 NP-hard8.7 Examples of Problems in Different Classes8.8 NP-completeness8.9 Reduction8.9.1 Computational Complexity8.9.2 0–1 Knapsack Problem8.9.3 Computational ComplexitySolved ProblemsSummaryShort AnswersFill in the BlanksObjective Question BankExercises
9. LR(k) and LL(1) Grammars
9.1 LL(1) Grammar9.2 Rules for Verifying Whether the Given Grammar Is LL(1) or Not9.3 LR(K) Grammars9.4 Properties of LR(k) Grammars9.5 Construction of LR(0) Items for Context Free Grammars9.6 Definition of LR(0) Grammar9.7 LR(1) GrammarSolved ProblemsSummaryShort AnswersFill in the BlanksObjective Question BankExercises
Appendix A: Proposition and Predicate Logic
A.1 PropositionsA.2 ConnectivesA.3 Well-Formed FormulaA.3.1 Truth Table for a Well-formed FormulaA.4 Logical IdentitiesA.5 Normal Forms of Well-formed FormalsA.5.1 Construction to Obtain a Disjunctive Normal Form of a Given FormulaA.6 Principal Disjunctive Normal FormA.6.1 Construction to Obtain the Principal Disjunctive Normal Form of a Given FormulaA.7 Predicate CalculusA.8 Universal and Existential QuantifierA.9 Well-formed Formulas of Predicate CalculusA.10 Rules of Inference for Predicate CalculusSummary
Appendix B: Frequently Asked University Questions with Solutions
Part A - Brief QuestionsPart B - Detailed Questions
References
Copyright

Content preview from Formal Languages and Automata Theory

Brief Contents

Preface

Acknowledgements

List of Important Symbols

List of Important Abbreviations

About the Authors

1. Mathematical Preliminaries and Formal Languages

2. Finite Automata

3. Regular Languages and Regular Grammars

4. Context Free Grammars and Context Free Languages

5. Push Down Automata

6. Turing Machines

7. Undecidability and Computability

8. Non-deterministic Polynomial Completeness

9. LR(k) and LL(1) Grammars

Appendix A: Proposition and Predicate Logic

Appendix B: Frequently Asked University Questions with Solutions

References

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 Automata Theory, Formal Languages and Computation

Publisher Resources

ISBN: 9789332558274

Cloud Computing

Data Engineering

Data Science

AI & ML

Programming Languages

Software Architecture

IT/Ops

Security

Design

Business

Soft Skills

Formal Languages and Automata Theory

by K.V.N. Sunitha

Brief 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.