[工學(xué)]有限自動機(jī)理論01章基礎(chǔ)知識(參考版)
2025-01-24 13:04本頁面
【正文】 ?所有倒數(shù)第 6個字符是 0的串的語言。 ?所有包含 3個連續(xù) 0的串的語言。 ?所有長度為奇數(shù)的串的語言。 ?所有最多有一對連續(xù)的 0或者最多有一對連續(xù)的 1的串的語言。 ?所有以 0開頭，以 1結(jié)尾的串的語言。 ?計算思維能力的培養(yǎng)主要是通過基礎(chǔ)理論系列課程實(shí)現(xiàn)的，該系列是由數(shù)學(xué)和抽象度較高的理論課程組成，包括數(shù)學(xué)分析、集合和圖論、形式語言與自動機(jī)、近世代數(shù)、數(shù)學(xué)建模等課程。 ?計算機(jī)學(xué)科系統(tǒng)地研究信息描述和變換算法 ， 重要包括信息描述和變換算法的理論 、 分析 、 效率 、 實(shí)現(xiàn)和運(yùn)用 。 ?計算機(jī)科學(xué)與技術(shù)學(xué)科要求學(xué)生具有形式化描述和抽象思維能力 ， 要求掌握邏輯思維方法 。 ?建立物理符號系統(tǒng)并對起實(shí)施等價變換是計算機(jī)學(xué)科進(jìn)行問題描述和求解的重要手段 。 ? 理論方面的知識是計算機(jī)的真正靈魂。這也是計算機(jī)科學(xué)與其他學(xué)科的重要區(qū)別。 ?實(shí)際上 ， 形式語言與自動機(jī)理論除了在計算機(jī)科學(xué)與技術(shù)領(lǐng)域的直接應(yīng)用外 ， 更在計算機(jī)計算機(jī)科學(xué)與技術(shù)領(lǐng)域的人才的計算思維能力的培養(yǎng)中占有極其重要的地位 。 當(dāng)計算機(jī)科學(xué)家絞盡腦汁尋找辦法來判斷一種程序語言是否有歧義性時 ， 喬姆斯基用形式語言理論的思想證明 ， 一個任意的上下文無關(guān)文法是否有歧義性是不可判定的 ， 因此 ， 屬于上下文無關(guān)文法的程序語言是否有歧義性也是不可判定的 。 ? 驗(yàn)證三：喬姆斯基用形式語言理論的思想證明了計算機(jī)科學(xué)的一個重大理論問題：計算機(jī)程序語言是否有歧義性是不可判定的 。 而喬姆斯基的 3型文法 ——正則文法 ， 在研究文字的計算機(jī)模式識別時 ， 也被有效應(yīng)用 。 ? 驗(yàn)證二：計算機(jī)所使用的各種高級語言 ， 如ALGOL、 FORTRAN、 PASCAL、 C、 LISP 等 ，都遵循一種程序語言文法描述的范式 ， 即巴科斯 —諾爾范式 。 ” ? 喬姆斯基的形式語言理論得到過計算機(jī)科學(xué)的三種驗(yàn)證 。 ? 形式語言理論的研究對象與以前的所有語言研究不同 ， 不止自然語言 ， 而是人類一切語言：既有自然語言 ， 也有人工語言 ，包括計算機(jī)編程的高級語言 。 ? 尤其是上下文無關(guān)文法 ， 被作為計算機(jī)程序設(shè)計語言語法的最佳近似描述得到了較為深入的研究 。 使用巴科斯 諾爾范式 （ BNFBackusNaur Form） 成功地對高級程序設(shè)計語言 ALGOL60的詞法和語法規(guī)則進(jìn)行了形式化的描述 （ 實(shí)際上 ， 巴科斯 諾爾范式就是上下文無關(guān)文法的產(chǎn)生式另一種表示方式 ） 。 并被置于數(shù)學(xué)的光芒之下 。 ? Chomsky于 1959年 ， 將他本人的形式語言的研究成果和 Kleene的自動機(jī)的研究成果結(jié)合起來 ， 不僅確定了文法和自動機(jī)分別從產(chǎn)生和識別角度定義語言 ， 而且證明了文法與自動機(jī)的等價性 。 一個語言 ， 可以采取不同的描述方式：文法產(chǎn)生語言和自動機(jī)識別語言 。 Kleene在研究神經(jīng)細(xì)胞時建立了自動機(jī)模型 ， Kleene使用該模型來識別 （ 接收 ） 一個語言：按照某種識別規(guī)則構(gòu)造自動機(jī) ， 該自動機(jī)就定義了一個語言 ， 該語言由自動機(jī)能夠識別的所有字符串構(gòu)成 。 ? 1959年 ， Chomsky根據(jù)產(chǎn)生語言的文法的產(chǎn)生式的不同特點(diǎn) ， 將文法和對應(yīng)產(chǎn)生的語言分為三大類 。 1956年 ， 通過抽象 ，Chomsky將語言形式地定義為由一個字母表的字母組成的一些串的集合：對于任意語言 L， 有一個字母表 ， 使得 LC∑*。 語言與句子 設(shè) ?是一個字母表， ?L ? ?*, L稱為字母表 ?上的一個 語言 ?x ? L, x稱為 L的一個 句子 。 串的長度 |ε|=0； |ω|= n； 若 ω=a1a2a3… an； 其中： ai∈ ， n0； 11)前綴和后綴： x,y,z∈ ∑*， 且 x=yz y是 x的前綴； 如果 z ? ε， 則稱 y是 x的 真前綴 ； z是 x的后綴； 如果 y?ε， 則稱 z是 x的 真后綴 ； 例 113 串 abcde： 前綴： ε， a， ab， abc， abcd， abcde 真前綴： ε， a， ab， abc， abcd 后綴： ε， e， de， cde， bcde， abcde 真后綴： ε， e， de， cde， bcde 對于任意字符串 x， x的前綴有 |x|+1 個 真前綴有 | x | 個 對于任何字符串 x， x的任意 前綴 y有惟一 的一個 后綴 z與之對應(yīng) ， 使得 x=yz，反之亦然； 對于任何字符串 x， x的任意 真前綴 y有 惟一 的一個 真后綴 z與之對應(yīng) ， 使得x=yz， 反之亦然 （ 除了 ε以外 ） ； 對于任何字符串 x x是 自身的前綴 ， 但 不是真前綴 x是 自身的后綴 ， 但 不是真后綴 對于任何字符串 x ? ε， ε是 x的前綴 ， 且是真前綴； ε是 x的后綴 ， 且是真后綴； 思考： 對于 ε， 前綴是 ？ 真前綴 ？ 后綴是 ？ 真后綴 ？ 12)語言的前綴性質(zhì) 設(shè) L是某個字母表上的語言 如果 L中的任何句子都是另一個句子的真前綴 ， 則稱語言 L具有 前綴性質(zhì) 。 本質(zhì)上 ， 語言 L是 字母表 ∑上的字符串形成的 集合 。 A= 216。 |{?}|=1 |216。 思考 : AB與 BA在什么情況下相等 ? 1)當(dāng) A=B； 2)A或 B中有一個為 {ε},則 A{ε}={ε}A=A 3)A和 B中有一個為 Ф， 則 AФ=ФA=Ф 6)An代表集合 A的 n次連接 (冪 ) A的 n次 冪 定義為： (1) A0 = {?} (2) An = An1A n ? 1 7) A*代表 A上所有字符串的集合 即表示集合 A中的所有字符串進(jìn)行 任意次 連接 而形成的串的集合 A*稱為集合 A的閉包 (克林閉包 ) A* = A0 ∪ A1 ∪ A2 ∪ … ∪ An 例 A={0， 1} A0={ε} 即 長度為 0的 0和 1組成的串的集合 A1=A={0,1} 即 長度為 1的 0和 1組成的串的集合 A2=AA={00,01,10,11} 即 長度為 2的 0和 1組成的串集合 A3=A2A ={000,001,010,011,100,101,110,111} 即 長度為 3的 0和 1組成的串的集合 … A* = A0 ∪ A1 ∪ A2 ∪ … ∪ An ={0和 1 組成的所有的串 } ={w|w是 0和 1 組成的串 } 如果串 ω是集合 A的閉包中的串 ，也稱 ω是集合 A上的串 。 則 ??= a1a2a3… anb1b2b3… bm。 (3) 用 ?代表字母表 。 常用術(shù)語 (1) 用 ?代表空串 ， {?}代表僅含有空串的集合 。 注意：并不是所有的無窮語言都存在 有窮表示
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1