🤖形式语言与自动机—期末笔记
status
Published
type
Post
date
May 12, 2026
slug
fla-final
summary
本文为课程所有内容的简要提炼，包括自动机的形式化定义、学到的所有语言的定义（及对应的自动机）和性质，迁移系统
tags
形式语言与自动机
category
期末复习
icon
password
Automata
DFA =
PDA =
- 或
- ID 是一个三元组 表示当前状态为 ，剩余输入为 ，栈内容为 ，左侧是栈顶
- 一个 ID 序列：
- P 是一个 PDA， 表示通过终止状态定义的 PDA 语言， 表示通过空栈定义的 PDA 语言
- 和 表达能力等价
CFG PDA
CFG → PDA：PDA 的每一步代表某个左句型 (Left-Sentential Form, LSF)，即最左推导中的一步
- 构造通过空栈接受的 PDA
- 终结符号：弹栈
- 非终结符：猜测一个产生式，并替换
PDA → CFG：
- 已知根据空栈接受的 PDA ，构造一个上下文无关文法使得
- 每一个状态形如 ，表示从状态 在弹出栈顶符号为 后到达状态
- 对 PDA 的每一个产生式（只考虑简单情况）：
- 若 ，说明 PDA 读取 之后直接弹出 并从 走到 ，因此
- 若 ，说明 PDA 读取 之后走到了 并用 替换了 ，因此
- 若 ，说明 PDA 读取 之后走到了 ，并用 替换了 。为了删除 ， 需要先删除 ，从状态 走到某个状态 ，然后删除 ，从状态 走到状态 。这里需要对所有可能的状态 生成产生式：
注：这里可能生成一些无用产生式（不可达），但是为了算法的正确性，是必要的
CYK 算法
CYK 算法是一种动态规划算法，用于在 时间判断字符串 是否在上下文无关文法 描述的上下文无关语言 中
注： 是 CNF
算法流程：
- 画出下三角矩阵， 的 向右增大， 向上增大
- 基本情况：最下面一行，使用单终结符产生式
- 归纳：对其余单元格（代表的子串），尝试所有分割，并匹配产生式。类似的运行顺序如下：
- 最后检查初始符号 是否在 中（即最左上角的单元格）
CFL → CNF
上下文无关文法的范式化过程：NULL Unit useless
- 去除空产生式
- 发现空产生式：使用归纳法。如果 那么 可空，如果 且 中的符号都是可空的，那么 可空
- 去除空产生式：
- 添加：对于每一个产生式，将右边可空符号的（所有）子集去掉得到新的产生式
- 删除：删掉所有的 产生式
- 去除单元产生式：将所有的 且 替换为
- 去除无用符号
- 符号有用指的是它出现在了某个从起始符号到某个终结字符串的推导中
- 删除无用符号，两步的顺序不能颠倒：
- 删除不能导出终结字符串的符号
- 删除不可达符号
CNF 范式：
- 每个产生式都是以下两种形式的一种
All Language
RE, R
递归可枚举语言（RE）是图灵机定义的语言。
RE 指的是存在一个图灵机 ，如果输入 在语言中， 保证停机且给出 ，但是若 不在语言中，没有保证。
算法是通过终止状态接收的图灵机，无论是否接收都会停机。
算法定义的语言是递归语言（R），也叫图灵可判定语言。
可判定（decidability）问题：membership testing，即是否有一个算法，对于一个输入 (x)，都可以说明 (x) 是否属于语言。
封闭性
语言的逆：指的是将 中所有字符串倒过来（Reverse）
同态：指的是一个函数，将字母表中的每个字符映射到字符串
逆同态：逆同态 作用在语言上，表示所有的源字符串 ，这些 经过同态函数落在 中，即
正则语言在以下操作封闭：
- 并，拼接，星闭包，交，差，补
- 逆（用归纳法）
- 同态（代入正则表达式）
- 逆同态（根据 的 DFA 构造一个 DFA，）
上下文无关语言在以下操作封闭：
- 并，拼接，星闭包
- 逆
- 同态，逆同态
CFL 在以下操作不封闭：
- 交集，差集
CFL RL = CFL，这个性质可以证明一个语言不是 RL
递归语言对交并补差封闭
自动机的能力
不同自动机等价性（空栈，终止状态）
正则表达式，DFA，NFA，-NFA 等价
下推自动机
- NPDA 的 和 等价，均可以描述 CFL
- NPDA 的表达能力比 DPDA 强（考虑 ）
- 的表达能力弱于
- DPDA （通过空栈接受）不能 cover RL，考虑前缀语言 ，DPDA 在接受 时就已经空栈了，无法处理
- RE 和 DPDA(N(P)) 是交叉关系
泵引理
正则语言的泵引理：
上下文无关语言的泵引理：
归约用常见语言
常见语言（不可判定，NP等）
迁移系统（建模时序电路）
经典题目（给出几个公式，画出 TS）。自然语言 -> 形式化。实际应用题：给出一个自然语言描述的系统，使用最后讲的 TS, Petri Net, TA 进行建模。给出一些归约，使用CTL描述。
根据定义写 TS，分为三步：
- 状态空间
- 初始状态
- 转移
注意：画迁移系统时，先将所有状态枚举出来，然后再考虑这些状态上的转移。有一些状态是不可达的，这些状态也需要列出来。
CTL 谓词
CTL 考点：
Safety, Liveness, Fairness
Loading...