A Second Course in Formal Languages and Automata Theory - No Information Available

Instant online reading.
Don't wait for delivery!

A Second Course in Formal Languages and Automata Theory

By: No Information Available

Write A Review

Hardcover | 27 October 2008

At a Glance

Hardcover
254 Pages

Dimensions(cm)
22.86 x 15.24 x 1.75

Hardcover

RRP $119.95

$103.75

14%OFF

or 4 interest-free payments of $25.94 with

or

Ships in 5 to 7 business days

Intended for graduate students and advanced undergraduates in computer science, A Second Course in Formal Languages and Automata Theory treats topics in the theory of computation not usually covered in a first course. After a review of basic concepts, the book covers combinatorics on words, regular languages, context-free languages, parsing and recognition, Turing machines, and other language classes. Many topics often absent from other textbooks, such as repetitions in words, state complexity, the interchange lemma, 2DPDAs, and the incompressibility method, are covered here. The author places particular emphasis on the resources needed to represent certain languages. The book also includes a diverse collection of more than 200 exercises, suggestions for term projects, and research problems that remain open.

Industry Reviews

'First courses in automata theory are now essential for both mathematicians and computer scientists, and there are some fine books from which one can learn the basics. But the question is: what next? ... There is ... a niche for second courses on automata theory that point the way to future study in the field without bludgeoning the reader under the weight of pages. At a shade under 250 pages Jeffrey Shallit's book is just such a second course. ... The writing is crisp and no nonsense ... Shallit has written a mathematically rigorous book that has avoided the pitfall of being unduly fussy.' SIAM Review

Shipping

	Standard Shipping	Express Shipping
Metro postcodes:	$9.99	$14.95
Regional postcodes:	$9.99	$14.95
Rural postcodes:	$9.99	$14.95

Orders over $79.00 qualify for free shipping.

How to return your order

At Booktopia, we offer hassle-free returns in accordance with our returns policy. If you wish to return an item, please get in touch with Booktopia Customer Care.

Additional postage charges may be applicable.

Defective items

If there is a problem with any of the items received for your order then the Booktopia Customer Care team is ready to assist you.

For more info please visit our Help Centre.

More in Mathematical Theory of Computation

Algorithms in C, Parts 1-4

3rd Edition - Fundamentals, Data Structures, Sorting, Searching

Paperback

RRP $131.20

$81.75

38%
OFF

Swim Training Patterns : 1st Edition - Plan your Training Sessions with the Power of Mathematics - Christoph Bartneck

$117.75

AI Engineering : Building Applications with Foundation Models - Chip Huyen

$73.75

51%
OFF

Introduction to Modern Cryptography

Chapman & Hall/Crc Cryptography and Network Security

Hardcover

RRP $242.00

$233.75

Exploring Complex Networks with Quantum Walks

Hardcover

RRP $137.00

$123.99

Mathematics for Artificial Intelligence

Textbooks in Mathematics

Paperback

RRP $90.99

$82.75

Machine Learning Interviews

Kickstart Your Machine Learning Career

Paperback

RRP $152.00

$73.75

51%
OFF

Introduction to Modern Cryptography : Revised Third Edition - Jonathan Katz

$219.75

13%
OFF

Crypto Engine Design

Cyber Shorts

Paperback

RRP $105.00

$92.75

12%
OFF

Quantum Computing : Foundations and Practice - Steven Herbert

$73.75

51%
OFF

Machine Learning Pocket Reference

Working with Structured Data in Python

Paperback

RRP $57.00

$30.75

46%
OFF

Preface	p. ix
Review of formal languages and automata theory	p. 1
Sets	p. 1
Symbols, strings, and languages	p. 1
Regular expressions and regular languages	p. 3
Finite automata	p. 4
Context-free grammars and languages	p. 8
Turning machines	p. 13
Unsolvability	p. 17
Complexity theory	p. 19
Exercises	p. 21
Projects	p. 26
Research problems	p. 26
Notes on Chapter 1	p. 26
Combinatorics on words	p. 28
Basics	p. 28
Morphisms	p. 29
The theorems of Lyndon-Schutzenberger	p. 30
Conjugates and borders	p. 34
Repetitions in strings	p. 37
Applications of the Thue-Morse sequence and squarefree strings	p. 40
Exercises	p. 43
Projects	p. 47
Research problems	p. 47
Notes on Chapter 2	p. 47
Finite automata and regular languages	p. 49
Moore and Mealy machines	p. 49
Quotients	p. 52
Morphisms and substitutions	p. 54
Advanced closure properties of regular languages	p. 58
Transducers	p. 61
Two-way finite automata	p. 65
The transformation automaton	p. 71
Automata, graphs, and Boolean matrices	p. 73
The Myhill-Nerode theorem	p. 77
Minimization of finite automata	p. 81
State complexity	p. 89
Partial orders and regular languages	p. 92
Exercises	p. 95
Projects	p. 105
Research problems	p. 105
Notes on Chapter 3	p. 106
Context-free grammars and languages	p. 108
Closure properties	p. 108
Unary context-free languages	p. 111
Ogden's lemma	p. 112
Applications of Ogden's lemma	p. 114
The interchange lemma	p. 118
Parikh's theorem	p. 121
Deterministic context-free languages	p. 126
Linear languages	p. 130
Exercises	p. 132
Projects	p. 138
Research problems	p. 138
Notes on Chapter 4	p. 138
Parsing and recognition	p. 140
Recognition and parsing in general grammars	p. 141
Earley's method	p. 144
Top-down parsing	p. 152
Removing LL(1) conflicts	p. 161
Bottom-up parsing	p. 163
Exercises	p. 172
Projects	p. 173
Notes on Chapter 5	p. 173
Turing machines	p. 174
Unrestricted grammars	p. 174
Kolmogorov complexity	p. 177
The incompressibility method	p. 180
The busy beaver problem	p. 183
The Post correspondence problem	p. 186
Unsolvability and context-free languages	p. 190
Complexity and regular languages	p. 193
Exercises	p. 198
Projects	p. 200
Research problems	p. 200
Notes on Chapter 6	p. 200
Other language classes	p. 202
Context-sensitive languages	p. 202
The Chomsky hierarchy	p. 212
2DPDAs and Cook's theorem	p. 213
Exercises	p. 221
Projects	p. 222
Research problems	p. 222
Notes on Chapter 7	p. 223
Bibliography	p. 225
Index	p. 233
Table of Contents provided by Ingram. All Rights Reserved.

A Second Course in Formal Languages and Automata Theory

At a Glance

Hardcover

Industry Reviews

Shipping

How to return your order

Defective items

You Can Find This Book In

More in Mathematical Theory of Computation

Algorithms in C, Parts 1-4

3rd Edition - Fundamentals, Data Structures, Sorting, Searching

Swim Training Patterns

1st Edition - Plan your Training Sessions with the Power of Mathematics

Discrete Mathematics for Computing

Grassroots

AI Engineering

Building Applications with Foundation Models