计算机理论基础

形式语言

这个寒假遇到的一些问题让我想起之前形式语言与自动机的内容，程序执行的本质是状态的变化，我觉得有必要将这部分理论捡起来，需要的时候方便自己回忆。

概念整理

  • 形式语言 是形式化描述的 字母表 上的 字符串 的集合。字母表 为字符的有限集合，多用 T 表示；字符串 指字母表中的字符构成的 有限 序列。
  • 自动机 接受一定的输入，执行一定的动作，产生一定的结果。使用状态迁移描述整个过程。例如可实现一个用于识别字符串的自动机系统，根据输入的字符串解析形式语言。状态 是一个标识，用于区分自动机在不同时刻的状况；自动机的本质是 根据状态、输入和规则决定下一个状态 （状态迁移）。
  • 有限自动机可以认为是由一个带有读写头的有限控制器和一条写有字符的输入带组成。
  • 关系：
    形式语言非限定性语言上下文有关语言上下文无关语言正则语言
    自动机图灵机线性有界自动机下推式存储自动机有限自动机

语言及文法

  • 字符串的运算：字符串 ω 的长度记为 |ω|， ω 的逆记为 ω^T。字符串的 连接 满足结合律，且有 εω = ωε = ω，|ω1ω2| = |ω1| + |ω2|。空串 ε 是任何串的前/后缀和字串。
  • 字母表的 幂运算：设 T 为字母表，n∈N。
    1. T0 = {ε}
    2. 设 x∈T(n-1)，a∈T，则 ax∈Tn
    3. Tn 中的元素只能由 (1) 和 (2) 构成
  • 闭包（*）：T* = Σ Tk (k = 0..n) = T0 ∪ T1 ∪ ... ∪ Tn，闭包（+）：T+ = Σ Tk (k = 1..n)，即 T* = T+ ∪ {ε}。
  • 语言：T 为字母表，任何集合 L ⊆ T* 是字母表 T 上的一个语言。
    • 积运算：L1 与 L2 的积是 L1 和 L2 中字符串相连的集合，不满足交换律
    • 幂运算：L0 = {ε}, Ln = L · L(n-1) = L(n-1) · L (n ≥ 1)
    • ∅ 表示不存在任何句子的语言，{ε} 表示仅存在空句子的语言
  • 文法：用来定义语言的数学模型称为文法。
    • 语言 L 为有限集合：通过列举表示
    • 语言 L 为无限集合，通过文法产生系统或机器识别系统
    • 元语言：描述语言的语言，文法是一种元语言
  • BNF（巴科斯范式）：
1
2
3
<数字> ::= 0 | 1 | 2 | .. | 9
<字母> ::= A | B | C | .. | Z | a | b | c | .. | z
<标识符> ::= <字母> | <标识符><字母> | <标识符><数字>
  • Chomsky 文法体系：任何一种文法必包含有：两个不同的有限符号集合（终结符号集合 N 和非终结符号集合 T）；一个形式化规则的有限集合 P （又称生成式集合）；一个起始符 S。
  • 文法的 形式定义 ：文法 G 是一个四元组，G = (N, T, P, S)。其中 N ∩ T = ∅；P 为形式为 α → β 的生成式 有限 集合，且 α ∈ (N∪T)* N+ (N∪T)*，β ∈ (N∪T)*；S 是起始符，S ∈ N。

推导和句型

  • 直接推导：G = (N, T, P, S)，有 A → β 是 P 中的生成式，α 和 γ 均属于 (N ∪ T)*，则 αAγ ⇒ αβγ 称 αAγ 直接导出 αβγ，或者说 αβγ 是 αAγ 的直接推导；
  • 推导序列：α = α0 ⇒ α1 ⇒ ... ⇒ αn 是长度为 n 的推导序列，α = α0 是长度为 0 的推导序列。对 α 推导出 α’，记为 α ⇒(*, G) α'，若 α 推导出 α’ 用了长度大于 0 的推导序列，则记为 α ⇒(+, G) α'。推导序列的每一步都会产生一个字符串，这些字符串称为 句型。
  • 字符串 α 是文法 G 的句型，当且仅当 S ⇒(*, G) α，且 α ∈ (N ∪ T)*。句型包含 句子，ω 是 G 的句子，当且仅当 S ⇒(*, G) ω 且 ω ∈ T*，即必须由起始符集合 S 推导出，并且由终结符集合构成的。
  • 例：括号匹配语言，定义集合基本元素 ()，递归产生其他句子：若 S 为合法串，则 (S) 和 SS 均合法。故 P 中包含三种生成式：S → (); S → (S); S → SS。

Chomsky 文法体系分类

  • 0 型文法：无限制文法 ⇒ 无限制语言，递归可枚举语言（图灵机）
  • 1 型文法：上下文有关文法，CSG ⇒ 上下文有关语言，CSL（线性有界自动机，LBA）
    • 生成式形式：α → β，其中 |α| ≤ |β|, β ∈ (N ∪ T)+, α ∈ (N ∪ T)* N+ (N ∪ T)*，即满足生成式的 左侧短于右侧 ，且 不包含 A → ε 。
    • 应用：过程式语言调用时形参与实参的一致性检查。
  • 2 型文法：上下文无关文法，CFG ⇒ 上下文无关语言，CEL（下推自动机，PDA）
    • 生成式形式：A → B，其中 A ∈ N, β ∈ (N ∪ T)*，可以包含 A → ε。
    • 每个生成式左侧都是 单个非终结符。
  • 3 型文法：正则文法 ⇒ 正则语言（有限自动机，FSA）
    • 左线性文法：A → Bω 或 A → ω，其中 A, B ∈ N, ω ∈ T*；
    • 右线性文法：A → ωB 或 A → ω，其中 A, B ∈ N, ω ∈ T*。
  • 已知语言求特定文法，得到的文法不是唯一的。
  • 几种文法之间关系：
    • 0 型：无限制，包括 1、2、3 型文法；
    • 1 型：不允许 A → ε，包含不含 A → ε 的 2、3 型文法
    • 2 型：包含 3 型文法

专栏目录：计算机理论基础
此专栏的上一篇文章：无
此专栏的下一篇文章：有限自动机

参考资料：《形式语言与自动机》，王柏、杨娟编著，北京邮电大学出版社

原创作品，允许转载，转载时无需告知，但请务必以超链接形式标明文章原始出处(http://blog.forec.cn/2017/02/25/formal-languages-and-automata1/) 、作者信息（Forec）和本声明。

分享到