Introduction

Formal Languages and Automata Theory are one of the most important base fields of (Theoretical) Computer Science. They are rooted in the middle of the last century, and these theories find important applications in other fields of Computer Science and Information Technology, such as, Compiler Technologies, at Operating Systems, ... Although most of the classical results are from the last century, there are some new developments connected to various fields.

The authors of this book have been teaching Formal Languages and Automata Theory for 20 years. This book gives an introduction to these fields. It contains the most essential parts of these theories with lots of examples and exercises. In the book, after discussing some of the most important basic definitions, we start from the smallest and simplest class of the Chomsky hierarchy. This class, the class of regular languages, is well known and has several applications; it is accepted by the class of finite automata. However there are some important languages that are not regular. Therefore we continue with the classes of linear and context-free languages. These classes have also a wide range of applications, and they are accepted by various families of pushdown automata. Finally, the largest classes of the hierarchy, the families of context-sensitive and recursively enumerable languages are presented. These classes are accepted by various families of Turing machines. At the end of the book we give some further literature for those who want to study these fields more deeply and/or interested to newer developments.

The comments of the lector and some other colleagues are gratefully acknowledged.

Debrecen, 2014.