離散數(shù)學(xué)-屈婉玲(形式語言與自動機(jī)).ppt

《離散數(shù)學(xué)-屈婉玲(形式語言與自動機(jī)).ppt》由會員分享，可在線閱讀，更多相關(guān)《離散數(shù)學(xué)-屈婉玲(形式語言與自動機(jī)).ppt（15頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1 11 4圖靈機(jī) 圖靈機(jī)的基本模型圖靈機(jī)接受的語言 遞歸可枚舉語言用圖靈機(jī)計算函數(shù) 部分可計算函數(shù)與可計算函數(shù) 2 問題的提出 1900年D Hilbert在巴黎第二屆數(shù)學(xué)家大會上提出著名的23個問題 第10個問題 如何判定整系數(shù)多項式是否有整數(shù)根 要求使用 有限次運算的過程 1970年證明不存在這樣的判定算法 即這個問題是不可判定的 或不可計算的 3 計算模型 從20世紀(jì)30年代先后提出圖靈機(jī)A M Turing 1936年 轉(zhuǎn)換演算A Church 1935年遞歸函數(shù)K G del 1936年正規(guī)算法A A Markov 1951年無限寄存器機(jī)器J C Shepherdson 1963年 4 Church Turing論題 已經(jīng)證明這些模型都是等價的 即它們計算的函數(shù)類 識別的語言類 是相同的 Church Turing論題 直觀可計算的函數(shù)類就是圖靈機(jī)以及任何與圖靈機(jī)等價的計算模型可計算 可定義 的函數(shù)類 5 圖靈機(jī)的基本模型 定義圖靈機(jī) TM M Q q0 B A 其中 1 狀態(tài)集合Q 非空有窮集合 2 輸入字母表 非空有窮集合 3 帶字母表 非空有窮集合且 4 初始狀態(tài)q0 Q 控制器 6 圖靈機(jī)的基本模型 續(xù) 5 空白符B 6 接受狀態(tài)集A Q 7 動作函數(shù) 是Q 到 L R Q的部分函數(shù) 即dom Q q s s R q 的含義 當(dāng)處于狀態(tài)q 讀寫頭掃視符號s時 M的下一步把狀態(tài)轉(zhuǎn)移到q 讀寫頭把這個s改寫成s 并向右移一格 q s s L q 的含義類似 只是讀寫頭向左移一格 若 q s 沒有定義 則M停機(jī) 7 一個TMM的實例 例1 8 格局 帶的內(nèi)容 當(dāng)前的狀態(tài)和讀寫頭掃視的方格 q 其中 q Q初始格局 0 q0w 其中w 是輸入字符串接受格局 q q A停機(jī)格局 qs q s 沒有定義 1 2 從 1經(jīng)過一步能夠到達(dá) 2 稱 2是 1的后繼 1 2 從 1經(jīng)過若干步能夠到達(dá) 2 圖靈機(jī)的計算 9 圖靈機(jī)的計算 續(xù) 計算 一個有窮的或無窮的格局序列 序列中的每一個格局都是前一個格局的后繼 w M從 0 q0w開始的計算有3種可能 1 停機(jī)在接受格局 即計算為 0 1 n 其中 n是接受的停機(jī)格局 2 停機(jī)在非接受格局 即計算為 0 1 n 其中 n是非接受的停機(jī)格局 3 永不停機(jī) 即計算為 0 1 n 10 圖靈機(jī)接受的語言 定義 w 如果M從 0 q0w開始的計算停機(jī)在接受格局 則稱M接受輸入串w M接受的語言L M 是M接受的所有輸入串 即L M w M接受w 例1 續(xù) M關(guān)于輸入w 10100的計算 q010100B 1q00100B 10q0100B 101q000B 1010q00B 10100q0B 1010q10B 101q20BB 101Bq3BB由于停機(jī)在接受格局 故M接受10100 L M w00 w 0 1 11 圖靈機(jī)接受的語言 續(xù) 定義能被圖靈機(jī)接受的語言稱作遞歸可枚舉的 記作r e 定理語言L是r e 當(dāng)且僅當(dāng)L是0型語言 圖靈機(jī)與0型文法是等價的 12 用圖靈機(jī)計算函數(shù) 上的m元部分字函數(shù) m的某個子集到 的部分函數(shù)TMM計算的m元部分字函數(shù)f 設(shè)輸入字母表為 x1 xm 如果M從初始格局 0 q0 x1B xmB開始的計算停機(jī) 不管是否停機(jī)在接受狀態(tài) 從停機(jī)時帶的內(nèi)容中刪去 以外的字符 得到字符串y 則f x1 x2 xm y 如果M從初始格局 0開始的計算永不停機(jī) 則f x1 x2 xm 沒有定義 記作f x1 x2 xm 例1 續(xù) M計算函數(shù) x 0 1 13 數(shù)論函數(shù) 數(shù)論函數(shù) 自然數(shù)集合N上的函數(shù)N上的m元部分函數(shù)N上的m元全函數(shù) 在Nm的每一點都有定義例如x y是全函數(shù) x y是部分函數(shù) 當(dāng)x y時 x y 一進(jìn)制表示 用1x表示自然數(shù)x例如111表示3 空串 表示0數(shù)論函數(shù)的一進(jìn)制表示 字母表 1 上的字函數(shù) 用一進(jìn)制表示自然數(shù)例如x y可表成f 1x 1y 1x y 14 遞歸函數(shù) 定義設(shè)f是N上的m元部分函數(shù) 如果圖靈機(jī)M計算f的一進(jìn)制表示 即M的輸入字母表為 1 x1 xm N 從初始格局 0 開始 若f x1 xm y 則M的計算停機(jī) 且停機(jī)時帶的內(nèi)容 不計 1 以外的字符 為1y 若f x1 xm 則M永不停機(jī) 那么稱M以一進(jìn)制方式計算f 定義圖靈機(jī)M以一進(jìn)制方式計算的N上的m元部分函數(shù)稱作部分遞歸函數(shù) 或部分可計算函數(shù) 部分遞歸的全函數(shù)稱作遞歸函數(shù) 或可計算函數(shù) 15 遞歸函數(shù) 續(xù) 例1 續(xù) M以一進(jìn)制方式計算 這是一個部分遞歸函數(shù)