Muutke küpsiste eelistusi

Formal Languages and Automata Theory [Pehme köide]

4.14/5 (14 hinnangut Goodreads-ist)
(Assistant Professor, YMCA University of Science and Technology, Faridabad)
  • Formaat: Paperback / softback, 380 pages, kõrgus x laius x paksus: 241x185x18 mm, kaal: 514 g, 100 figures
  • Ilmumisaeg: 24-Apr-2012
  • Kirjastus: OUP India
  • ISBN-10: 019807106X
  • ISBN-13: 9780198071068
Teised raamatud teemal:
Formal Languages and Automata TheorySuurem pilt
  • Formaat: Paperback / softback, 380 pages, kõrgus x laius x paksus: 241x185x18 mm, kaal: 514 g, 100 figures
  • Ilmumisaeg: 24-Apr-2012
  • Kirjastus: OUP India
  • ISBN-10: 019807106X
  • ISBN-13: 9780198071068
Teised raamatud teemal:
Püsilink: https://www.kriso.ee/db/9780198071068.html
Märksõnad:

Formal Language and Automata Theory is designed to serve as a textbook for undergraduate students of B..E, B.Tech. CSE, and MCA/IT. It attempts to help students grasp the essential concepts involved in automata theory.

The book starts with basic concepts such as discrete mathematical structures and fundamentals of automata theory, which are prerequisites for understanding further topics. Description of important topics such as regular sets and grammar, context free languages, and various types of automata such as DFA, NDFA, push down, LBA, and Turing Machine is then taken up in detail. Special emphasis is laid on design and applications of Turing Machines. Finally, the book focuses on decidability factor of recursively enabled languages and the complexity problem dealing with the relation between P and NP classes.

Written in a lucid and student-friendly manner the book contains a large number of solved examples. Each chapter consists of a set of chapter-end exercises, which aid students in acquiring better understanding of the concepts. It also provides appendices on Church-Turing thesis, Godel numbering, chronology of some important events, and a write-up paying homage to all the scientists who have contributed significantly in shaping this subject area to its present form.
Preface v
Abbreviations xv
1 Automata, Formal Languages, and Computability
1(16)
1.1 Formal Languages
2(8)
1.1.1 Phrase Structure Grammars
3(6)
1.1.2 Sentential Forms
9(1)
1.2 Chomsky Classification of Grammars
10(3)
1.2.1 Classifying the Type of Grammar
11(2)
1.3 Computability
13(4)
Supplementary Examples
13(4)
2 Mathematical Preliminaries
17(37)
2.1 Set Theory
17(8)
2.1.1 Cardinality of a Set
18(1)
2.1.2 Defining the Set
18(1)
2.1.3 Subset
18(1)
2.1.4 Venn Diagrams
19(1)
2.1.5 Null Set
19(1)
2.1.6 Power Set
19(1)
2.1.7 Universal Set
19(1)
2.1.8 Set Operations
20(2)
2.1.9 Partition Set
22(1)
2.1.10 Properties Related to Set Operations
23(2)
2.2 Relations
25(4)
2.2.1 Types of Relations
26(3)
2.2.2 Relative Set
29(1)
2.3 Functions
29(2)
2.3.1 Types of Functions
30(1)
2.3.2 Composition of Functions
31(1)
2.4 Counting Techniques
31(4)
2.4.1 Permutations
31(2)
2.4.2 Combinations
33(2)
2.4.3 Pigeonhole Principle
35(1)
2.5 Logic
35(5)
2.5.1 Propositions and Logic Operations
35(2)
2.5.2 Conditional Statements
37(1)
2.5.3 Properties of Logical Operations
38(2)
2.6 Methods of Proof
40(14)
2.6.1 Direct Proof
41(1)
2.6.2 Indirect Proof
41(1)
2.6.3 Mathematical Induction
42(2)
Supplementary Examples
44(10)
3 Finite Automata
54(46)
3.1 Finite Automata
55(3)
3.1.1 String Processing by Finite Automaton
56(1)
3.1.2 Language of Finite Automaton
57(1)
3.2 Extended Transition Function and its Properties
58(3)
3.3 Deterministic and Nondeterministic Finite Automata
61(1)
3.3.1 Acceptance of String by NFA
62(1)
3.4 Equivalence of NFA and DFA
62(7)
3.4.1 Converting NFA to its Equivalent DFA
63(4)
3.4.2 Equivalence of DFAs
67(2)
3.5 Level Equivalence and Reduction in Finite Automata
69(4)
3.6 Finite Automata with Outputs
73(3)
3.6.1 Moore and Mealy Machines
74(1)
3.6.2 Conversion of Moore Machine to Equivalent Mealy Machine
74(1)
3.6.3 Conversion of Mealy Machine to Equivalent Moore Machine
75(1)
3.7 Finite Automata with Null Moves
76(7)
3.7.1 Removal of Null Moves
78(5)
3.8 Finite Automata and Sequential Circuits
83(3)
3.8.1 Shift Register as Moore Machine
83(1)
3.8.2 Shift Register as Mealy Machine
84(1)
3.8.3 Design Considerations in Moore and Mealy Machines
85(1)
3.9 Using Finite Automata in Software Design
86(14)
Supplementary Examples
87(13)
4 Regular Grammar and Regular Sets
100(43)
4.1 Regular Expression
100(1)
4.2 Correspondence between Regular Expression and Regular Set
101(3)
4.3 Identities Related to Regular Expressions
104(1)
4.4 Relation between Regular Languages and Finite Automata
105(13)
4.4.1 Finite Automaton Corresponding to Regular Expression
106(6)
4.4.2 Regular Expression Corresponding to Finite Automata
112(6)
4.5 Closure Properties of Regular Sets
118(2)
4.6 Automata for Union, Intersection, and Difference of Languages
120(5)
4.7 Pumping Lemma for Regular Languages
125(2)
4.7.1 Applications of Pumping Lemma
126(1)
4.7.2 Suitability of Pumping Lemma
127(1)
4.8 Production System Associated with Regular Grammar
127(1)
4.9 Myhill Nerode Theorem (Equivalent Classes and Regular Languages)
128(2)
4.10 Some Decision Problems Related to Finite Automata and Regular Languages
130(2)
4.11 Regular Languages and Current Programming Language Scenario
132(11)
Supplementary Examples
133(10)
5 Context-free Grammars and Languages
143(50)
5.1 Some Examples of Recursive Grammars
143(3)
5.2 Context-free Grammars
146(17)
5.2.1 Leftmost and Rightmost Derivation of Strings
148(1)
5.2.2 Some Examples of Context-free Languages and Grammars
148(2)
5.2.3 Ambiguity in Context-free Grammar and Parse Tree
150(3)
5.2.4 Possible Defects in CFGs and their Removal
153(10)
5.3 Context-free Languages as Superset of Regular Languages
163(3)
5.4 Closure Properties of Context-free Languages
166(5)
5.4.1 Nonclosure Properties
169(2)
5.5 Normal Forms for Context-free Grammar
171(7)
5.5.1 Chomsky Normal Form
171(3)
5.5.2 Greibach Normal Form
174(4)
5.6 Pumping Lemma for Context-free Grammars
178(3)
5.6.1 Applications of Pumping Lemma
179(1)
5.6.2 Ogden's Lemma
180(1)
5.7 Applications of Context-free Grammars
181(12)
5.7.1 Programming Language Constructs
181(2)
5.7.2 Natural Language Constructs
183(1)
5.7.3 Markup Languages
184(2)
Supplementary Examples
186(7)
6 Pushdown Automata
193(32)
6.1 Basic Structure of Pushdown Automata
194(9)
6.2 Two Types of Acceptance by PDA
203(1)
6.3 Correspondence between PDA and CFL
204(5)
6.3.1 PDA Corresponding to Given CFG
204(2)
6.3.2 CFG Corresponding to Given PDA
206(3)
6.3.3 Deterministic PDA and Deterministic CFL
209(1)
6.4 Parsing and PDA
209(16)
6.4.1 Removal of Left Factoring
212(1)
6.4.2 Removal of Left Recursion
213(1)
6.4.3 Parsing Process
213(9)
Supplementary Examples
222(3)
7 Turing Machines
225(54)
7.1 Basic Structure and Working of Turing Machine
225(16)
7.2 Instantaneous Description of Turing Machine
241(1)
7.3 Language of Turing Machine
241(1)
7.4 Turing Machine as Computer for Positive Integers
242(5)
7.5 Universal Turing Machine
247(2)
7.6 Enhancements in Turing Machine
249(9)
7.6.1 Multitrack Turing Machine
249(7)
7.6.2 Multitape Turing Machine
256(2)
7.7 Turing Machine as Enumerator
258(1)
7.8 Nondeterministic and Deterministic Turing Machine
259(1)
7.9 Alternative Representation of Turing Machines
260(4)
7.9.1 Turing Machine with One-way Infinite Tape
260(2)
7.9.2 Two-stack Machine
262(2)
7.10 Time and Space Complexity of Turing Machine
264(3)
7.11 Some Other Machines
267(12)
7.11.1 Linear-bound Automata
267(1)
7.11.2 Post Machine
267(4)
Supplementary Examples
271(8)
8 The Pitfall of Algorithmic Computing: Undecidability
279(21)
8.1 Recursive and Non-recursive Languages
280(5)
8.1.1 Recognition and Acceptance
281(4)
8.2 Language of Turing Machines
285(15)
8.2.1 Decision Problems Relating to Turing Machines
288(1)
8.2.2 Reduction
289(2)
8.2.3 Decision Problems Relating to Context-free Grammar
291(2)
8.2.4 Post Correspondence Problem
293(1)
8.2.5 Constructing CFG using PCP
294(2)
Supplementary Examples
296(4)
9 Computable Functions
300(17)
9.1 Primitive Recursive Functions
300(11)
9.1.1 Composition of Functions
301(1)
9.1.2 Initial Functions
301(1)
9.1.3 Defining Functions by Primitive Recursion
302(4)
9.1.4 Turing Machine for Constant Functions
306(1)
9.1.5 Turing Machine for Successor Functions
307(1)
9.1.6 Turing Machine for Projection Functions
307(4)
9.2 μ-Recursive Functions
311(6)
9.2.1 Computability and μ-Recursive Functions
312(1)
Supplementary Examples
312(5)
10 Computational Complexity: Tractable and Possibly Intractable Problems
317(20)
10.1 Growth Rates of Functions
318(2)
10.1.1 O (Big-oh)
319(1)
10.1.2 (Big-theta)
320(1)
10.1.3 o (Little-oh)
320(1)
10.2 Languages and Complexity Classes
320(2)
10.2.1 Complexity Classes
321(1)
10.3 Decision and Optimization Problems
322(1)
10.4 Classes P and NP
322(3)
10.4.1 CNF Satisfiability Problem
323(1)
10.4.2 Hamiltonian Cycle Problem
324(1)
10.5 Polynomial Time Reduction
325(1)
10.5.1 Algorithm for Polynomial Time Reduction
326(1)
10.5.2 Reduction and Tractability/Intractibility
326(1)
10.6 NP-complete Problems
326(7)
10.6.1 k-Colourability Problem
333(1)
10.6.2 Vertex Cover Problem
333(1)
10.7 Significance of Discovering NP-complete Problems
333(1)
10.8 Some Misconceptions about NP-complete Problems
334(3)
Supplementary Examples
334(3)
Appendix A Church-Turing Thesis 337(2)
Appendix B Godel Numbering 339(2)
Appendix C Homage to Key Scientists 341(3)
Appendix D Chronology of Some Important Events 344(1)
Index 345
Chander Kumar Nagpal is currently working as Assistant Professor in YMCA University of Science & Technology, Faridabad. A PhD in computer science from Jamia Milia Islamia University he has close to 30 years of teaching experience.

An expert in his field, Chander Kumar Nagpal has designed course materials on subjects such as Computer Programming, Artificial Intelligence, and System Analysis and Design for Indian Society for Technical Education (ISTE). He has also published several research papers in various journals of national and international repute.