Formal Languages and Computation: Models and Their Applications

This computer science book gives a clear, comprehensive introduction to formal language theory and its applications in computer science. It is meant as the basis of a one-term course on this subject at the undergraduate level. It covers all rudimental topics concerning formal languages and their models, especially grammars and automata. It sketches the basic ideas underlying the theory of computation, including computability, decidability, and computational complexity. From a practical viewpoint, it explains how these models underlie computer science engineering techniques for language processing, such as lexical and syntax analysis.