3. 形式语言入门¶
3.1. 引言¶
在本模块中，我们介绍本学期的三个基础概念：语言、文法和自动机。
3.2. 语言¶
首先，我们介绍与语言（Language）有关的基本概念——这里按形式语言（Formal Languages）学科中的用法来使用这个词。
3.3. 文法¶
下面的框架集介绍文法（grammar）的概念——这里同样按形式语言学科中的用法来使用。
3.4. 文法练习¶
3.5. 自动机¶
现在，我们明白了语言是什么（字母表上的串的某个子集），也明白了文法是什么（一种用产生式（production）规则定义语言的方式）。 我们的第三个主要概念是一族被称为 自动机 的计算模型。 自动机应当被看作简单的计算机。 “简单”的好处在于，我们可以期望完全理解各种类型的机器有多“强大”。 这里的“强大”是指它们可以被编程来 识别 哪些语言，也就是可靠地判断一个串是否属于该语言。
上面这幅图展示了“计算机”的物理组成部分，但并没有展示它的控制行为（即当我们处于某个状态、当前纸带方格上是某个符号、存储单元当前位置是某个值时，要做什么）。 这种控制行为就像计算机的“软件”。 用来控制这台机器的“程序”将是一组规则：检查当前纸带上的字母和机器的当前状态，然后决定转移到哪个状态。 有些类型的机器每步自动把纸带头向右移动一格。 有些机器能够改写当前方格中的符号，而且也许还能选择是向右还是向左移动。
