Discrete Structures And Automata Theory,9781842652565

Discrete Structures And Automata Theory

by ; ;
ISBN13: 9781842652565
ISBN10: 1842652567
Format: Hardcover
Pub. Date: 2006-01-30
Publisher(s): Alpha Science International
Availability: This title is currently not available.
List Price: $59.36

Rent Textbook

Select for Price
Add to Cart
There was a problem. Please try again later.

New Textbook

We're Sorry
Sold Out

Used Textbook

We're Sorry
Sold Out

eTextbook

We're Sorry
Not Available

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

An electronic version of this book is available through VitalSource.

This book is viewable on PC, Mac, iPhone, iPad, iPod Touch, and most smartphones.

By purchasing, you will be able to view this book online, as well as download it, for the chosen number of days.

Digital License

You are licensing a digital product for a set duration. Durations are set forth in the product description, with "Lifetime" typically meaning five (5) years of online access and permanent download to a supported device. All licenses are non-transferable.

More details can be found here.

A downloadable version of this book is available through the eCampus Reader or compatible Adobe readers.

Applications are available on iOS, Android, PC, Mac, and Windows Mobile platforms.

Please view the compatibility matrix prior to purchase.