
- 自动机理论教程
- 自动机理论 - 首页
- 自动机理论 - 入门
- 自动机理论 - 历史
- 自动机理论 - 应用
- 自动机理论术语
- 自动机中字符串的基础知识
- 自动机的集合论
- 语言和文法
- 计算理论中的文法
- 由文法生成的语言
- 乔姆斯基文法分类
- 有限自动机
- 确定性有限自动机 (DFA)
- 非确定性有限自动机 (NFA)
- 从 NFA 到 DFA 的转换
- DFA 的最小化
- Moore 机与 Mealy 机
- DFA 的补集
- 正则表达式
- 自动机中的正则表达式
- 自动机中的 Arden 定理
- 将正则表达式转换为有限自动机
- 正则文法的泵引理
- 计算理论中的正则集
- 上下文无关文法
- 上下文无关文法 (CFG)
- 上下文无关文法中的二义性
- 上下文无关语言的闭包性质
- 简化上下文无关文法
- 乔姆斯基范式 (CNF)
- 格雷巴赫范式 (GNF)
- 上下文无关文法的泵引理
- 下推自动机
- 下推自动机 (PDA)
- 下推自动机的接受
- 从 CFG 构造 PDA
- 下推自动机和语法分析
- 图灵机
- 图灵机 (TM) 基础
- 图灵机接受的语言
- 多磁带图灵机
- 多轨迹图灵机
- 非确定性图灵机
- 半无限带图灵机
- 线性界限自动机 (LBA)
- 可计算性和不可判定性
- 图灵语言的可判定性
- 不可判定语言
- 图灵机停机问题
- 计算理论中的 Rice 定理
- Post 对应问题 (PCP)
- 自动机理论资源
- 自动机理论 - 快速指南
- 自动机理论 - 资源
- 自动机理论 - 讨论
对应邮局问题
对应邮局问题 (PCP) 由 Emil Post 于 1946 年提出,是一个不可判定的判定问题。在字母表 ∑ 上的 PCP 问题陈述如下:
给定以下两个列表,**M** 和 **N**,它们包含在 ∑ 上的非空字符串:
M = (x1, x2, x3,………, xn)
N = (y1, y2, y3,………, yn)
如果对于某些 i1,i2,………… ik,其中 1 ≤ ij ≤ n,条件 xi1 …….xik = yi1 …….yik 成立,则可以说存在 Post 对应解。
示例 1
查找列表
M = (abb, aa, aaa) 和 N = (bba, aaa, aa)
是否存在 Post 对应解?
解答
x1 | x2 | x3 | |
---|---|---|---|
M | abb | aa | aaa |
N | bba | aaa | aa |
这里:
x2x1x3 = ‘aaabbaaa’
并且 y2y1y3 = ‘aaabbaaa’
我们可以看到
x2x1x3 = y2y1y3
因此,解为 i = 2, j = 1, k = 3.
示例 2
查找列表 M = (ab, bab, bbaaa) 和 N = (a, ba, bab) 是否存在 Post 对应解?
解答
x1 | x2 | x3 | |
---|---|---|---|
M | ab | bab | bbaaa |
N | a | ba | bab |
在这种情况下,不存在解,因为:
| x2x1x3 | ≠ | y2y1y3 | (长度不相等)
因此,可以说这个 Post 对应问题是不可判定的。
广告