A Second Course in Formal Languages and Automata Theory
Published on 8. September 2008
Book
Hardback
254 pages
978-0-521-86572-2 (ISBN)
Description
Written 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.
Reviews / Votes
'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 ReviewMore details
Language
English
Place of publication
Cambridge
United Kingdom
Target group
College/higher education
Illustrations
Worked examples or Exercises; 12 Tables, unspecified
Dimensions
Height: 235 mm
Width: 157 mm
Thickness: 20 mm
Weight
568 gr
ISBN-13
978-0-521-86572-2 (9780521865722)
Copyright in bibliographic data and cover images is held by Nielsen Book Services Limited or by the publishers or by their respective licensors: all rights reserved.
Schweitzer Classification
Other editions
Additional editions
Jeffrey Shallit
A Second Course in Formal Languages and Automata Theory
E-Book
11/2008
1st Edition
Cambridge University Press
€58.99
Available for download
Person
Jeffrey Shallit is Professor of the David R. Cheriton School of Computer Science at the University of Waterloo. He is the author of Algorithmic Number Theory (co-authored with Eric Bach) and Automatic Sequences: Theory, Applications, Generalizations (co-authored with Jean-Paul Allouche). He has published approximately 90 articles on number theory, algebra, automata theory, complexity theory, and the history of mathematics and computing.
Content
1. Review of formal languages and automata theory; 2. Combinatorics on words; 3. Finite automata and regular languages; 4. Context-free grammars and languages; 5. Parsing and recognition; 6. Turing machines; 7. Other language classes.