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

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

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