《理論計算機科學基礎》第7講

《理論計算機科學基礎》第7講1第6周(不)可計算問題第4章丘奇-圖靈論題第5章可判定性第6章可歸約性第7章可計算性理論的高級專題《理論計算機科學基礎》第7講2第5章可判定性可判定語言關于正則語言的可判定問題關于上下文無關語言的可判定問題停機問題對角化方法停機問題是不可判定的非圖靈可識別語言《理論計算機科學基礎》第8講3第6章可歸約性語言理論中的不可判定問題利用計算歷史的歸約線性界限自動機波斯特對應問題映射歸約(多一歸約,m歸約)《理論計算機科學基礎》第7講4算法可解性的局限算法可解存在處處停機的算法按照算法可解性給問題分類證明有些問題能用算法求解證明另一些問題不能用算法求解研究不可解性的意義避免做無用功激發(fā)想象力,全面透徹地理解

什么是計算《理論計算機科學基礎》第7講5可判定語言問題與語言編碼可判定性存在處處停機的TM程序關于正則語言的

可計算問題《理論計算機科學基礎》第7講6《理論計算機科學基礎》第7講7關于正則語言的可判定問題DFA接受性問題NFA接受性問題正則表達式派生性問題DFA空性問題DFA等價性問題《理論計算機科學基礎》第7講8DFA接受性問題DFA接受性問題檢測一個給定的確定型有窮自動機是否接受一個給定的串語言

ADFA={<B,w>|DFAB接受串w}

DFAB接受串w

<B,w>ADFA.《理論計算機科學基礎》第7講9定理5.1定理5.1:ADFA是可判定語言證明思路:設計一個判定ADFA的TMM.M模擬B在w上的計算想象一下寫上述程序所需要的細節(jié)《理論計算機科學基礎》第7講10定理5.1證明證明:設計一個判定ADFA的TMM.

M=“對輸入<B,w>,

其中B是DFA,w是串:1)在輸入w上模擬B.2)若模擬以接受狀態(tài)結束,

則接受;

若模擬以非接受狀態(tài)結束,

則拒絕.”《理論計算機科學基礎》第7講11定理5.1證明證明:(續(xù))TMM首先檢查輸入<B,w>,

若w不是字符串,或B不是

(Q,,,q0,F)形式,則拒絕.然后M執(zhí)行模擬.

M通過在帶上寫下信息,來跟蹤B

在w上運行時當前狀態(tài)和當前位置.

狀態(tài)和位置的更新

由B的轉移函數(shù)確定.

當M處理完w最后一個符號時,如果B

處于接受狀態(tài),則M接受,否則拒絕.#《理論計算機科學基礎》第7講12NFA接受性問題NFA接受性問題檢測一個給定的非確定型有窮自動機是否接受一個給定的串語言

ANFA={<B,w>|NFAB接受串w}《理論計算機科學基礎》第7講13定理5.2定理5.2:ANFA是可判定語言證明思路:證法一:用NTMN模擬NFAB在w上計算證法二:先把NFAB轉化為等價的DFAC,

再用TMM模擬C在w上計算《理論計算機科學基礎》第7講14定理5.2證明證明:構造判定ANFA的TMN.N=“對于輸入<B,w>,

B是NFA,w是串:

1)把NFAB轉化成等價DFAC

(定理2.19).

2)在輸入<C,w>上運行TMM

(定理5.1).

3)如果M接受,則接受,

否則拒絕.”#《理論計算機科學基礎》第7講15正則表達式派生性問題正則表達式派生性問題一個正則表達式是否派生

一個給定的串語言AREX={<R,w>|正則表達式R派生串w}《理論計算機科學基礎》第7講16定理5.3證明證明:下面的TMP判定AREX.P=“對于輸入<R,w>,R是RE,w是串:1)把REXR轉化成等價DFAA(定理2.28).2)在輸入<A,w>上運行TMM

(定理5.1).3)如果M接受,則接受,

否則拒絕.”#《理論計算機科學基礎》第7講17說明對于可判定性問題,

把DFA,NFA,REX

提供給TM都是等價的,

因為TM能在這三種編碼

之間進行互相轉換.《理論計算機科學基礎》第7講18DFA空性問題DFA空性問題一個DFA是否根本不接受

任何串?語言

EDFA={<A>|A是DFA且

L(A)=

}《理論計算機科學基礎》第7講19定理5.4定理5.4:EDFA是可判定語言證明思路:逐個檢查所有的串有無窮多個串DFA接受一個串當且僅當:從初始狀態(tài)出發(fā),

沿著此DFA的箭頭方向,能夠到達一個接受狀態(tài)采用例4.14的標記算法《理論計算機科學基礎》第7講20定理5.4證明證明:TMT=“對于輸入<A>,

A是DFA:1)標記初始狀態(tài).2)重復下列步驟,直到所有狀態(tài)

都被標記.3)對于一個狀態(tài),如果有一個到達

它的轉移是從某個已經(jīng)標記

過的狀態(tài)出發(fā)的,則將它標記.4)如果沒有接受狀態(tài)被標記,

則接受,否則拒絕.”#《理論計算機科學基礎》第7講21DFA等價性問題DFA等價性問題檢查兩個DFA是否識別

同一個語言語言

EQDFA={<A,B>|A和B是DFA且

L(A)=L(B)}《理論計算機科學基礎》第7講22定理5.5定理5.5:EQDFA是可判定語言證明思路:正則語言對于布爾運算封閉,

因此對于對稱差運算封閉兩個語言相等當且僅當其對稱差為空語言正則語言是否為空,

這是可判定的(定理5.4)L(A)L(B)《理論計算機科學基礎》第7講23定理5.5證明證明:

TMF=“對于輸入<A,B>,

A和B都是DFA: