
- 自動機理論教程
- 自動機理論 - 首頁
- 自動機理論 - 入門
- 自動機理論 - 歷史
- 自動機理論 - 應用
- 自動機理論術語
- 自動機中字串的基礎知識
- 自動機的集合論
- 語言和文法
- 計算理論中的文法
- 由文法生成的語言
- 喬姆斯基文法分類
- 有限自動機
- 確定性有限自動機 (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 對應問題是不可判定的。
廣告