Discrete Structures And Automata Theory

by Dube, R.; Pandey, A.; Gupta, Ritu

• ISBN13: 9781842652565
• ISBN10: 1842652567
• Format: Hardcover
• Copyright: 2006-01-30
• Publisher: Alpha Science International

Summary

Discrete Structures and Automata Theory is designed for an introductory course on formal languages, automata and discrete mathematics. Divided into two parts it covers discrete methods - stressing the finite nature in many problems and structures; combinatorics – the algebra of enumeration or coding and finite algebraic structures - effecting coding theory, method of enumeration, gating networks and combinatorial designs. It also discusses the applications of Automata Theory in Compiler design, Natural Language Processing and development of new programming languages.

Table of Contents

Preface	v
Set Theory	1	(34)
Introduction	1	(8)
Venn Diagram	9	(1)
Set Operations	10	(2)
Laws of the Algebra of Sets	12	(12)
Generalized Unions and Intersections	24	(1)
Symmetric Difference of Two Sets	25	(1)
Duality of Sets	26	(9)
Relations	35	(38)
Introduction	35	(1)
Ordered Pairs	36	(1)
Cartesian Product of Sets	37	(2)
Relations	39	(1)
Types of Relations	40	(1)
Restriction of Relation to a Set	41	(1)
Properties of Binary Relation	41	(2)
Congruence Modulo Relation on Set of All Integers	43	(1)
Equivalence Relation	43	(6)
Closure Property of Relation	49	(2)
Representation of Relations	51	(1)
Composition of Relations	52	(1)
Partial Order Relation	53	(1)
Partition of A Set	54	(1)
Equivalence Classes (or Sets)	54	(2)
Circular Relation	56	(17)
Functions	73	(40)
Introduction	73	(1)
Definitions	74	(1)
Well-defined Function	74	(1)
Domain & Range of A Function	74	(1)
Representation of A Function	75	(1)
Graph of A Function	75	(1)
Equality of Two Functions	75	(3)
Types of Functions	78	(7)
Composition (or Product) of Functions	85	(1)
Some Theorems	86	(27)
Lattices	113	(29)
Introduction	114	(1)
Partially Ordered Set or Poset	114	(1)
Comparability	114	(1)
Totally Ordered Set	115	(1)
Well Ordered Set	115	(1)
Product Sets and Order	115	(1)
Lexicographic Ordering	115	(1)
Hasse Diagrams	115	(2)
External Elements of Partially Ordered Sets	117	(2)
Lattices	119	(1)
Sublattices	120	(1)
Isomorphic Lattices	121	(1)
Properties of Lattices	122	(1)
Special Types of Lattices	123	(3)
Join-Irreducible Elements	126	(1)
Atom	126	(1)
Duality	127	(1)
Complete Lattice	127	(1)
Meet-Irreducible Elements	127	(15)
Theory of Groups	142	(18)
Introduction (Algebraic Structures)	143	(1)
Groups	143	(1)
Abelian Group	144	(1)
Order of A Group	144	(1)
Semi-group	144	(1)
Some General Properties of Groups (Theorems)	145	(2)
Sub-groups	147	(1)
Some General Properties of Sub-groups (Theorems)	148	(1)
Integral Powers of An Element	149	(1)
Cyclic Groups	150	(1)
Theorems on Cyclic Groups	150	(1)
Addition and Multiplication Modulo m, A Positve Integer	151	(1)
Homomorphism of Group	151	(1)
Isomorphism of Group	152	(1)
Order of A Group	152	(1)
Normal Sub-group	152	(1)
Quotient Group (Definition)	152	(4)
Theorems	156	(1)
Kernel (Definition)	156	(1)
Theorems	156	(1)
Fundamental Theorem of Homomorphism	157	(3)
Rings and Fields	160	(12)
Introduction	160	(1)
Ring	160	(2)
Some Special Classes of Rings	162	(2)
Some Theorems	164	(1)
Field and Its Axioms	165	(1)
Some Theorems	166	(1)
Sub-rings and Sub-fields	167	(5)
Discrete Numeric Functions	172	(22)
Introduction	172	(1)
Definition---Numeric Functions	172	(2)
Manipulation of Numeric Functions	174	(4)
Asymptotic Behaviour of Numeric Functions	178	(1)
Asymptotic Dominance	179	(1)
Big-O Notations	179	(1)
Some Theorems	180	(1)
Big-Omega and Big-Theta Notations	181	(13)
Generating Functions	194	(16)
Introduction	194	(1)
Generating Function (Definition)	195	(1)
Some Results	195	(5)
Extended Binomial Co-efficient	200	(1)
Extended Binomial Theorem	200	(1)
Counting Problems	201	(9)
Recurrence Relations	210	(28)
Introduction	210	(1)
Recurrence Relation	211	(1)
Order of the Recurrence Relation	211	(1)
Degree of the Recurrence Relation	212	(1)
Linear Recurrence Relation with Constant Co-efficients	212	(1)
Solution of Linear Recurrence Relations	212	(1)
Homogeneous Solutions	213	(5)
Particular Solutions	218	(1)
Total Solutions	219	(7)
Solution by the Method of Generating Functions	226	(12)
Boolean Algebra	238	(30)
Introduction	238	(1)
Boolean Expressions and Boolean Functions	239	(1)
Identities of Boolean Algebra	240	(1)
Duality	241	(1)
Boolean Algebra (Definition)	241	(1)
Some Theorems	242	(3)
Atom (Definition)	245	(3)
Disjunctive Normal Form (DN Forms)	248	(1)
Conjunctive Normal Form (CN Form)	248	(1)
Theorems	249	(6)
Algebra of Switching Circuits	255	(5)
Design of Circuits	260	(1)
Don't Care Conditions	261	(1)
Design of n-terminal Circuits	262	(2)
Non-parallel Series Circuits	264	(4)
Mathematical Reasoning/Propositional Calculus and Logic	268	(45)
Introduction	269	(1)
Proposition	269	(1)
Propositional Variables	269	(1)
Logical Connectives	270	(1)
Types of Statements	270	(1)
Truth Tables	270	(3)
Polish Notation	273	(1)
Propositions and Truth Tables	273	(3)
Negation of Compound Statements	276	(1)
Logical Equivalence	277	(1)
Algebra of Proposition	277	(2)
Conditional Proposition	279	(1)
Negation of Conditional Statement	280	(1)
Conditional Statements and Variations	280	(1)
Biconditional Proposition (or Statement)	281	(1)
Negation of Biconditional Statement	282	(1)
Derived Connectives	282	(2)
Tautologies and Contradictions	284	(1)
Principle of Substitution	285	(1)
Contingency	285	(1)
Arguments	286	(2)
Logical Implication	288	(1)
Rules of Inference	289	(1)
Predicates and Quantifiers	290	(2)
Universal Quantification	292	(1)
Existential Quantification	292	(1)
Binding Variables	293	(1)
Prepositional Function	293	(1)
Negating Quantifiers	294	(19)
Introduction to Automata	313	(57)
Historical Aspect of Automata	314	(1)
The Study of Automata Theory is Fruitful and Futeristic	314	(1)
Develop Your Feelings with The Automata	315	(1)
Alphabets	315	(1)
Strings	316	(1)
Languages	317	(1)
Kleene Closure	318	(1)
Finite Automata	319	(3)
Transition Graph	322	(2)
Simpler Notation for DFA's	324	(1)
The Language of a DFA	325	(7)
Extending Transition Function to Strings	332	(2)
Nondeterminism	334	(14)
Minimization of DFA's	348	(22)
Automata with Output	370	(19)
Introduction	370	(1)
Moore Machine	371	(4)
Mealy Machine	375	(6)
Equivalance of Mealy and Moore Machine	381	(8)
Regular Expression and Languages	389	(19)
Regular Expressions	389	(5)
Comprative study of Regular Expression, Regular Sets and Finite Automata	394	(1)
Construction of FA for Regular Expression	395	(4)
Construction of Regular Expression from DFA	399	(3)
Algebraic Laws for Regular Expressions	402	(6)
Properties of Regular Languages	408	(18)
Introduction	408	(1)
Proving Language is not to be Regular	408	(8)
Closure Properties of Regular Languages	416	(6)
Decision Properties of Regular Languages	422	(4)
Context-Free Grammar and Languages	426	(45)
Grammars	426	(1)
Context-free Grammars	427	(23)
Parse Tree	450	(5)
Parsing an Example of Context-free Grammar	455	(2)
Ambiguity in Grammars and Languages	457	(14)
Simplified Context-Free Grammar and It's Normal Form	471	(30)
Introduction	471	(1)
Reduction of Context-free Grammar	472	(10)
Chomsky Normal Form	482	(4)
Greibach Normal Form	486	(4)
Regular Grammars	490	(11)
Pushdown Automata	501	(18)
Introduction	501	(1)
Definition of Pushdown Automata	502	(10)
Pushdown Automata and Context-free Grammar	512	(7)
Properties of Context-Free Languages	519	(16)
Introduction	519	(3)
Periodicity Properties	522	(1)
The Pumping Lemma for CFL's	523	(4)
Decidiability	527	(8)
Turing Machine	535	(34)
Introduction	535	(1)
Turing Machine As Physical Computing Device	536	(1)
Formal Definition of Turing Machine	537	(1)
A String Accepted by a TM	538	(3)
Instantaneous Description	541	(1)
Transition Diagram	542	(2)
Turing Thesis	544	(1)
Turing Machine for Computing Functions	544	(4)
Turing Machine As Language Acceptors	548	(2)
Combining Turing Machine	550	(19)
Chomsky Hierarchy	569	(12)
Phrase-structure Grammar	569	(2)
Chomsky Hierachy	571	(2)
Unrestricted (Type-0) Grammar	573	(3)
Context-Sensitive Grammar	576	(1)
Linear Bounded Automata	576	(1)
Relation Between Classes of Language	577	(4)
Index	581