Automata theory and formal languages / Pallavi Chavan, Ashish Jadhav.

Format:

Book

Author/Creator:

Chavan, Pallavi, author.

Jadhav, Ashish, author.

Language:

English

Subjects (All):

Machine theory.

Formal languages.

Physical Description:

1 online resource (291 pages)

Place of Publication:

London, England : Academic Press, [2023]

Summary:

Automata Theory and Formal Languages presents the difficult concepts of automata theory in a straightforward manner, including discussions on diverse concepts and tools that play major roles in developing computing machines, algorithms and code. Automata theory includes numerous concepts such as finite automata, regular grammar, formal languages, context free and context sensitive grammar, push down automata, Turing machine, and decidability, which constitute the backbone of computing machines. This book enables readers to gain sufficient knowledge and experience to construct and solve complex machines. Each chapter begins with key concepts followed by a number of important examples that demonstrate the solution. The book explains concepts and simultaneously helps readers develop an understanding of their application with real-world examples, including application of Context Free Grammars in programming languages and Artificial Intelligence, and cellular automata in biomedical problems. Presents the concepts of Automata Theory and Formal Languages in an easy-to-understand approach Helps the readers understand key concepts by solving real-world examples. Provides the readers with a simple approach to connect the theory with the latest trend like software testing, cybersecurity, artificial intelligence, and machine learning. Includes a wide coverage of applications of automata theory and formal languages.

Contents:

Front Cover

Automata Theory and Formal Languages

Copyright

Contents

List of figures

List of tables

Biography

Preface

1 Background and fundamentals

1.1 Objectives and outcomes

1.2 Sets

1.2.1 Set operations

1.2.2 Set properties

1.2.3 Solved examples

1.3 Propositions and logic

1.3.1 Propositions

1.3.2 Logical connectives

1.3.3 Solved examples

1.4 Relations

1.4.1 Properties of relations

1.4.2 Solved examples

1.5 Automata theory fundamentals

1.5.1 Alphabet

1.5.2 String

1.5.3 Language

1.5.4 Solved problems

1.6 Need of automata theory and formal languages

1.7 Chapter summary

1.8 Multiple choice questions

1.9 Exercises

References

2 Finite automata and machines

2.1 Objectives and outcomes

2.2 Finite automation

2.3 Introduction to finite automata

2.3.1 Finite automata as language acceptor

2.4 Types of finite automata

2.5 Deterministic finite automata

2.5.1 String processing by DFA

2.5.2 DFA constructions

2.5.3 Complement of DFA

2.5.4 Minimization of DFA

2.6 Nondeterministic finite automata

2.7 NFA to DFA conversion

2.8 Finite automata with ε/λ moves

2.8.1 Representation of ε-NFA

2.8.2 ε/λ closures

2.8.3 λ-NFA to DFA conversion

2.9 Finite automata with output

2.9.1 Mealy machine

2.9.2 Moore machine

2.9.3 Conversion of Mealy machine to Moore machine

2.9.4 Conversion of Moore machine to Mealy machine

2.10 Chapter summary

2.11 Multiple choice questions

2.12 Exercises

3 Regular expressions, regular language and grammar

3.1 Objectives and outcomes

3.2 Regular expressions

3.2.1 Properties of regular expressions

3.2.2 Simplification of regular expressions

3.3 Relationship of finite automata and regular expressions.

3.4 Equivalence of finite automata and regular expression

3.4.1 Conversion of regular expression to finite automata

3.4.2 Conversion of finite automata to regular expression

3.5 Closure properties of regular languages

3.6 Pumping lemma

3.7 Chomsky hierarchy of languages

3.8 Concept of grammar

3.8.1 String derivation from grammar

3.8.2 Right linear grammar

3.8.3 Left linear grammar

3.8.4 Regular grammar

3.8.5 Linear grammar

3.8.6 Conversion of regular grammar to finite automata

3.8.7 Conversion of finite automata into regular grammar

3.9 Chapter summary

3.10 Multiple choice questions

3.11 Exercises

4 Context-free grammar

4.1 Objectives and outcomes

4.2 Context-free grammar

4.3 Context-free language

4.4 String derivations and parse trees

4.5 Ambiguity in CFG

4.6 Simplification of CFG

4.7 Normal forms of CFG

4.7.1 Chomsky normal form (CNF)

4.7.2 Greibach normal form (GNF)

4.8 Chapter summary

4.9 Multiple choice questions

4.10 Exercises

5 Pushdown automata

5.1 Objectives and outcomes

5.2 Introduction to PDA

5.3 Language of PDA

5.4 Deterministic PDA

5.5 Nondeterministic PDA

5.6 Equivalence of CFGs and PDA

5.6.1 Conversion of CFG to PDA

5.6.2 Conversion of PDA into CFG

5.7 Chapter summary

5.8 Multiple choice questions

5.9 Exercises

6 Turing machine

6.1 Objectives and outcomes

6.2 Introduction to Turing machines

6.2.1 Model of Turing machine

6.2.2 Designing Turing machines

6.2.3 Halting of Turing machine

6.3 Turing machine variants

6.3.1 Multitape Turing machine

6.3.2 Nondeterministic Turing machine

6.3.3 Universal Turing machine

6.4 Chapter summary

6.5 Multiple choice questions

6.6 Exercises

7 Applications of automata.

7.1 Objectives and outcomes

7.2 Applications of finite automata and regular expressions

7.3 Applications of grammars

7.4 Applications of pushdown automata

7.5 Applications of Turing machine

7.6 Concept of cellular automata

7.7 Chapter summary

7.8 Multiple choice questions

8 Automata theory with recent trends

8.1 Objectives and outcomes

8.2 Introduction

8.3 Automata and cybersecurity

8.3.1 System software

8.3.2 Network testing

8.3.3 Protocol testing

8.3.4 Cloud security testing

8.3.5 Application testing

8.4 Automata and artificial intelligence (AI)/machine learning (ML)

8.5 Chapter summary

8.6 Multiple choice questions

A Answers to multiple choice questions

B Notations

Index

Back Cover.

Notes:

Description based on print version record.

Includes bibliographical references and index.

Other Format:

Print version: Chavan, Pallavi Automata Theory and Formal Languages

ISBN:

9780323972178

OCLC:

1378391861