Название: 200 Problems on Languages, Automata, and Computation
Автор: Filip Murlak, Damian Niwinski, Wojciech Rytter
Издательство: Cambridge University Press
Год: 2023
Страниц: 267
Язык: английский
Формат: pdf (true)
Размер: 10.2 MB

Formal languages and automata have long been fundamental to theoretical computer science, but students often struggle to understand these concepts in the abstract. This book provides a rich source of compelling exercises designed to help students grasp the subject intuitively through practice. The text covers important topics such as finite automata, regular expressions, push-down automata, grammars, and Turing machines via a series of problems of increasing difficultly. Problems are organised by topic, many with multiple follow-ups, and each section begins with a short recap of the basic notions necessary to make progress. Complete solutions are given for all exercises, making the book well suited for self-study as well as for use as a course supplement. Developed over the course of the editors' two decades of experience teaching the acclaimed Automata, Formal Languages, and Computation course at the University of Warsaw, it is an ideal resource for students and instructors alike.

The book consists of two parts. Part I Problems, contains 200 problems, ranging from easy, through intermediate (unmarked), to hard and very hard. Some of the harder problems are well-known textbook theorems; we include them because, during the years of teaching the automata course, we have seen that under appropriate guidance students can rediscover a lot of classical material on their own, gaining deeper understanding and a greater sense of accomplishment. Problem statements are interleaved with concise definitions of key notions; for a deeper and broader background we refer to the work listed in the Further Reading section at the end of the book.

Part II, Solutions (collectively by 19 authors), contains full solutions to all 200 problems. The focus of the book is on creativity, rather than on practising specific methods, but many solutions build upon previous problems. Some initially simple ideas are further developed in a sequence of problems, the very order of problem statements guiding the students towards powerful methods.

The book has an index. It can help locate the definition of a key notion, like off-line Turing machine, and find problems related to a specific topic, like one-letter alphabet, or using a specific solution idea, like the fooling method.