Formal Languages and Computation: Models and Their Applications (Hardcover)

Formal Languages and Computation: Models and Their Applications gives a clear, comprehensive introduction to formal language theory and its applications in computer science. It covers all rudimental topics concerning formal languages and their models, especially grammars and automata, and sketches the basic ideas underlying the theory of computation, including computability, decidability, and computational complexity. Emphasizing the relationship between theory and application, the book describes many real-world applications, including computer science engineering techniques for language processing and their implementation.

• Covers the theory of formal languages and their models, including all essential concepts and properties
• Explains how language models underlie language processors
• Pays a special attention to programming language analyzers, such as scanners and parsers, based on four language models—regular expressions, finite automata, context-free grammars, and pushdown automata
• Discusses the mathematical notion of a Turing machine as a universally accepted formalization of the intuitive notion of a procedure
• Reviews the general theory of computation, particularly computability and decidability
• Considers problem-deciding algorithms in terms of their computational complexity measured according to time and space requirements
• Points out that some problems are decidable in principle, but they are, in fact, intractable problems for absurdly high computational requirements of the algorithms that decide them

In short, this book represents a theoretically oriented treatment of formal languages and their models with a focus on their applications. It introduces all formalisms concerning them with enough rigors 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. After studying this book, both student and professional should be able to understand the fundamental theory of formal languages and computation, write language processors, and confidently follow most advanced books on the subject.

《形式語言與計算：模型及其應用》提供了對形式語言理論及其在計算機科學中應用的清晰而全面的介紹。它涵蓋了所有有關形式語言及其模型的基礎主題，特別是文法和自動機，並概述了計算理論的基本思想，包括可計算性、可決定性和計算複雜性。強調理論與應用之間的關係，本書描述了許多現實世界的應用，包括語言處理的計算機科學工程技術及其實現。

本書的主要內容包括：
- 詳細介紹形式語言的理論及其模型，包括所有基本概念和性質
- 解釋語言模型如何支持語言處理器
- 特別關注基於四種語言模型（正則表達式、有限自動機、上下文無關文法和下推自動機）的編程語言分析器，如掃描器和解析器
- 討論圖靈機的數學概念，作為直觀程序概念的普遍接受的形式化
- 回顧計算理論的一般概念，特別是可計算性和可決定性
- 根據時間和空間需求，考慮問題決策算法的計算複雜性
- 指出一些問題原則上是可決定的，但實際上對於決定它們的算法的計算要求過高，因此是棘手的問題

總之，本書以理論為導向，重點介紹形式語言及其模型，並著重於其應用。它以足夠的嚴謹性介紹了所有相關的形式化，使所有結果都非常清晰和有效。每個複雜的數學部分都有直觀的解釋，因此即使是本書最複雜的部分也很容易理解。通過學習本書，學生和專業人士都應該能夠理解形式語言和計算的基本理論，撰寫語言處理器，並自信地閱讀該領域的高級書籍。