2nd, revised edition. The book of famous American scientists is devoted to the theory of automata and the corresponding formal languages ​ ​ and grammars - both regular and context-free. In the second part, various Turing machines are considered, with the help of which the concepts of solvable and insoluble problems are formalized, as well as the functions of time and capacitive assessment of the complexity of algorithms are determined. The presentation is strict, but accessible, and is accompanied by numerous examples, as well as tasks for self-solution. The book will be useful to readers of various categories - students, graduate students, researchers, teachers of higher educational institutions, as well as everyone who is interested in the mathematical foundations of modern computer technology.