形式语言与自动机理论：去单一产生式解析

"这篇资料主要讨论的是形式语言与自动机理论，包括形式语言的概念、自动机的历史和发展，以及它们在实际应用中的角色。" 在形式语言理论中，形式语言被视为句子的集合，这些句子是由特定规则（即字母按照一定规律组合成的字符串）构成的。形式语言的研究不涉及语义，而是专注于构成规则。这一领域的发展源于克林和乔姆斯基的工作，其中乔姆斯基在1956年提出了文法的概念来研究语言，并在1959年证明了文法与自动机的等价性。 自动机理论是研究抽象计算设备或“机器”的能力，以状态自动机为基础构建模型。图灵机在1930年代被提出，而有限状态自动机在1940至1950年代成为研究焦点。自动机在实际中有着广泛应用，如字符串匹配算法（如KMP），词法分析器，数字电路设计和通信协议验证。 形式语言与自动机理论的一个关键概念是去单一产生式，这是在上下文无关文法中的一个操作。给定一个非终结符A，它的链集合CA包含了所有可以从A推导出的字符串。这个集合可以通过以下规则构建： 1. A本身属于CA。 2. 如果B在CA中，并且B可以推导出C，那么C也属于CA。 3. CA中的元素是通过有限次使用上述规则产生的。 自动机和文法之间的关系揭示了语言的描述方式，例如正规表达式与有限自动机等价，用于描述简单的字符串模式；而文法则更适合描述递归结构的数据。此外，自动机是研究计算复杂性和可判定性问题的基础，包括区分可解问题和难解问题。 关于计算机与人脑的能力对比，有两种观点。一种认为计算机在解决某些问题（如不可判定问题）上不如人脑，而人脑能部分解决这些问题。另一种观点则主张计算机通过模拟所有图灵机，理论上可以等同于一个复杂变化的有限状态自动机，因此其能力可能与人脑相当。 在第一章的语言定义中，Chomsky在1956年给出了语言的定义，它是由特定字母表中的字符组成的字符串集合。这标志着对语言形式化描述的开始，为后续的理论发展奠定了基础。