第11章 計算模型

　　計算機能夠執行許多任務，提出一個問題就存在兩個問題：第一，它能否由計算機來完成？一旦知道這第一個問題是肯定的，就會問第二個問題，怎麼執行這個任務？計算模型是用來幫助回答這兩個問題的。

　　下面将讨論三種類型的計算模型：文法、有限狀态機和圖靈機。文法是用來産生一種語言中的詞，并且确定一個詞是否屬于一種語言。文法産生的形式語言不僅可以作為自然語言的模型，如英語，還可以作為程式設計語言的模型，如 Pascal, Fortran, Prolog, C 和 Java, 特别是，文法在編譯器的理論和構造中極為重要，在20世紀50年代，美國語言學家諾姆.喬姆斯基（Noam Chomsky）首先使用了下面将要讨論的文法。

　　在模組化中，使用着各種類型的有限狀态機，每個有限狀态機都有一個狀态集合（包括初始狀态）和一個輸入字母表，還有一個轉移函數，它對每個由狀态和輸入構成的對，指定一個狀态。有限狀态機的狀态使得它具有有限的存儲能力。在些有限狀态機對每個轉移産生一個輸出符号。這類機器可以用作許多機器的模型，如自動售貨機，延遲機，二進制加法器和語言識别器，我們還将讨論沒有輸出但具有終結狀态的有限狀态機，這樣的機器廣泛用于語言識别，它們所識别的串是這樣的串；由初始狀态動行到終結狀态。文法和有限狀态機的概念具有緊密的聯系， 我們将要刻畫有限狀态機所能識别的集合的特征，并且證明這些集合恰 恰就是某種類型文法所産生的集合。

　　然後引入圖靈機的概念。我們将說明怎麼用圖靈機來識别集合，還要證明怎麼用圖靈機計算數論函數。 最後讨論圖靈---丘奇論題：每個能行的計算都可以由圖靈機來完成。

11.1 語言和文法

11.1.1 引言

　　　　英語中，單詞能以各種方式進行組合，單詞的哪些組合可以構成有效的句子是由英國文法确定的。例如： the frog writes nearly (青蛙寫的字很勻稱)是一個有效的句子，因為它是由一個名詞短語 the frog 接一個動詞短語 writes nearly構成的， 其中名詞短語the frog 是由冠詞the 和名詞frog 組成的，動詞短語 writes nearly 是由動詞writes 和 副詞 nearly 組成的。 我們并不在意這是一個毫無意義的句子，因為我們隻關心句子的文法，或者形式，而不在意它的語義，或者說含義。我們也要指出， 詞的組合swims quickly mathematics 不是有效的句子，因為它不符合英文的文法的規則。

　　自然語言（即口頭語言），如英語、法語、德語或西班牙語，都極為複雜。事實上，對一個自然語言，看起來不大可能說出它的所有文法規則。将一個語言自動翻譯成另一個語言的研究引出了形式語言的概念。與自然語言不同，形式語言是由一組意義明确的文法規定定義的，文法規則不僅對于語言學和自然語言的研究十分重要，而且對于程式設計語言的研究也是很重要。

　　我們要用文法描述形式語言的句子。在程式設計語言的應用中，經常出現兩類問題：（1）怎麼能夠确定一組單詞是否組合成了形式語言的一個有效句子？（2）怎麼才能産生形式語言的一個有效句子。在考慮這兩類問題時，文法的使用十分有益。

　　在給出文法的技術定義之前，先描述文法的一個例子，這個例子産生英語的一個子集，此英語子集是用下列規則定義的，這些規則描述怎麼産生有效的句子，這些規則是：

　　1.句子是由一個名詞短語後接一個動詞短語形成的；

　　2.名詞短語是由一個冠詞接一個形容詞再接一個名詞組成，或者

　　3.名詞短語由一個冠詞接一個名詞組成；

　　4.動詞短語是由一個動詞接一個副詞組成，或者

　　5.動詞短語由一個動詞組成，

　　6.冠詞是a,或者

　　7.冠詞 the ; 

　　8.形容詞 是large,或者

　　9.形容詞是 hungry; 

　　10. 名詞是 rabbit, 或者

　　11.名詞是 mathematician; 

　　12. 動詞是 eats, 或者

　　13. 動詞是hops; 

　　14. 副詞是quickly, 或者

　　15.副詞是wildly,

從這些規則出發，使用一系列替代直到不能再應用規則，就能形成一個有效的句子。例如，沿着下列替代序列就能得到一個有效的句子：

　　句子

　　名詞短語　　　　動詞短語

　　冠詞　　形容詞　　　　名詞　　　　動詞短語

　　冠詞　　形容詞　　　　名詞　　　　動詞　　　　副詞

　　the 　　形容詞　　　　名詞　　　　動詞　　　　副詞

　　the 　　large　　　　   名詞　　　　動詞　　　　副詞

　　the 　　large 　　　　rabbit　　　　動詞　　　　副詞

　　the　　large 　　　　rabbit　　　　hops　　　　副詞

　　the 　　large   　　   rabbit　　　　hops     　　　quickly

　　容易看出，下面都是有效的句子： a hungry mathematician eats wildly, a large mathematician hops, the rabbit eats quickly，等等。 也可以看出，the quickly eats mathematician不是有效句子。

11.1.2  短語結構文法

　　在給出文法的形式定義之前，先引入一個小術語。

　　定義1　　詞彙表（字母表）V 是元素的一個有限的非空集合，其元素稱為符号，V 上一個詞（或句子）是由V 中元素組成的有限長度的串。空串（或零串）是沒有符号的串，記為λ， V 上所有詞的集合記為V*。 V上的一個語言是V*的一個子集。

　　注意　　空串λ是不包含任何符号的串，它不同于空集∅。 因而{λ} 是僅包含一個串的集合，此串為空集。

　　可以用多種方式來指明語言，一種方式是列出語言中的所有詞；還有另一種方式是給出一些标準，使得一個詞要在這個語言中，就必須滿足這些标準。本節将描述另一種重要方式，使用文法，如使用本節引言中給出的規則集合。為産生詞，文法提供下個由各種類型符号組成的集合和一個由規則組成的集合。要确切地說，文法有一個詞彙表V， V是一個由符号組成的集合，語言中的成分就是這些符号導出的。詞彙表中的某些元素不能由其它符号替換，這些元素稱為終始符；詞彙表中的其他成分可以用其他符号替換，它們被稱為非終結符。終結符和非終結符集合通常分别記為T 和N。在本書引言所給出的例子中，終結符集是{a, the, rabbit, mathematician, hops, eats, quickly, wildly}, 非終結符集是（句子，名詞短語，動詞短語，形容詞，冠詞，名詞，動詞，副詞）。詞彙表中有一個特殊的元素，我們總是從這個特殊元素開始定義其它的符号，此符号稱為初始符，記為S。 在引言的例子中，初始符是句子。由詞彙表V 中元素構成的所有串的集合記為V*.指明V*中的串能被什麼樣的串替代的規則稱為文法的産生式，指時w0可以替換w1的産生式記為w0→w1。 在本節引言所給的文法中，我們列舉了所有産生式。如果使用剛才定義的記号，其中第一個産生式為句子→名詞短語　　動詞短語。 我們以下列定義作為小結。

　　定義2　　一個短語結構文法　　G=(V, T, S, P)由下列四部分組成：詞彙表V， 由V 的所有終結符組成的V的子集合T，V的初始符S， 以及産生式集合P。集合V一T記為N,N中的元素稱為非終結符。P中的每個産生式的左邊必須至少包含一個非終結符。

　　例1　　設G=(V, T, S, P), 其中：V={a, b, A, B, S},  T={a, b}, S是初始符，P={S→ABa, A→BB, B→ab, AB→b}。 則G 是一個短語結構文法的例子。

　　我們對短語結構文法的産生式所産生的詞感興趣。

　　

轉載于:https://www.cnblogs.com/666638zhangqiang/p/8039955.html