Automata: Theory, Trends, and Applications

Alexander Meduna is Full Professor of Computer Science at the Brno University of Technology, Czech Republic. He has taught mathematics and computer science at various European, Asian, and American universities, including the University of Missouri, USA, where he spent a decade teaching advanced topics of the formal language theory and its applications in computer science. He is the author of several computer science books and many papers on the topic.

• Vita
• Scientific Work
• University Website

Tomáš Kožár is a distinguished PhD Student supervised by Alexander Meduna at the Faculty of Information Technology, Brno University of Technology, Czech Republic.

• University Website

This computer science book gives an in-depth account of the theory of automata and computation. It also covers modern trends in automata theory. Furthermore, the text maintains a balance between a theoretical and practical approach to its subject by presenting many applications of automata. It is meant as a monograph as well as the basis of a one-term course on this subject at the graduate level.

First and foremost, this computer science book gives an account of the classical automata theory, including finite automata, pushdown automata, and Turing machines. Simultaneously, it pays a special attention to the consequences following from this theory in terms of computability, decidability, and complexity. In this way, it explains the fundamentals of the theory of computation. Second, it overviews currently active trends in automata theory, such as jumping, deep pushdown, and regulated automata. Finally, the book also describes real practical use of automata in a variety of scientific areas, ranging from programming language processing through natural language syntax analysis up to computational musicology.

As far as the style of presentation is concerned, this book primarily represents a theoretically oriented treatment of automata and computability. All the formalisms concerning automata are introduced with enough rigor to make all results quite clear and valid. Every complicated mathematical passage is preceded by its intuitive explanation so that even the most complex parts of the book are easy to grasp. Secondarily, containing many useful algorithms, the present book also demonstrates how automata underlie several computer-science engineering techniques.

• Lectures (PDF)

• Ordered by appearance in the text.
• Last updated on 2024-06-12.
• Send additional errors and comments to: meduna@fit.vut.cz

• Page 281, Example 10.1
• Mistake in the definition of M: 2 as the left subscript of M can be omitted, f is missing in the set of states, and input symbols a, b, c are missing in the pushdown alphabet, so Γ should be {A, S, #, a, b, c}.
• In addition, the moves of M contain several mistakes as well: (1) the configuration resulting from 5th move should have already state f. (2) Then, additional pop-move is missing to read a from the input and the top of pushdown. (3) The application of rule 1fA → fc should result into configuration (f, cc, cc#). (4) Then, the following pop move (resulting in (f, cc, cc#)) is superfluous and should be omitted.
• The correct sequence of moves of M is

• Reported 2024-06-12 by Ondřej Koumar of Brno University of Technology.

• Page 344, Section 11.5 Bottum-Up Parsing
• Mistake in a precedence table with unary operator ¬ (logical negation). The cell in row i and column ¬ should be empty.
• Reported 2023-12-11 by Zbyněk Křivka of Brno University of Technology.

• Page 344, Section 11.5 Bottum-Up Parsing, paragraph Arithmetic Expressions with Right-Associative Operators
• The production rule S → SS should be S → S - S
• Reported 2023-12-18 by Zbyněk Křivka of Brno University of Technology.

The authors' thanks go to the readers who pointed out the errors.