[科普中國(guó)]-帕里克定理

在理論計(jì)算機(jī)科學(xué)中，帕里克定理指出，對(duì)于上下文無(wú)關(guān)語(yǔ)言，如果只關(guān)心其中每個(gè)終止符號(hào)出現(xiàn)的次數(shù)，而不考慮它們的順序，那么存在正則語(yǔ)言與其對(duì)應(yīng)。這個(gè)定理可用于確定具有給定數(shù)量終止符號(hào)的字符串是否能為上下文無(wú)關(guān)語(yǔ)法接受。1961年羅希特·帕里克第一次證明了它，論文于1966年再次發(fā)表。

定義及形式化表述令為一個(gè)字母。定義單詞的帕里克矢量為函數(shù)

，其中表示詞w中出現(xiàn)的次數(shù)。

一個(gè)子集是線性的，如果它形如

存在向量，使得。

一個(gè)子集是半線性的，如果它為有限多線性子集的并。

帕里克定理的形式化表述如下。令L為上下文無(wú)關(guān)語(yǔ)言。令 P(L)為L(zhǎng)單詞的帕里克矢量集，即。則P(L)是半線性的。

兩種語(yǔ)言可以等效互換，如果他們的帕里克矢量集相同。若S為任意半線性集，則對(duì)單詞的帕里克矢量位于S中的語(yǔ)言，可等效于某些正則語(yǔ)言。因此，每一個(gè)上下文無(wú)關(guān)語(yǔ)言都可等效于某些正則語(yǔ)言。1

重要性帕里克定理表明，有些上下文無(wú)關(guān)語(yǔ)言可能只有歧義語(yǔ)法Template:Explain。這樣的語(yǔ)言稱為固有歧義語(yǔ)言。從形式文法的角度看，這意味著某些有歧義的上下文無(wú)關(guān)文法無(wú)法轉(zhuǎn)換為明確的上下文無(wú)關(guān)文法。2

上下文無(wú)關(guān)文法在計(jì)算機(jī)科學(xué)中，形式語(yǔ)言是：某個(gè)字母表上，一些有限長(zhǎng)字串的集合，而形式文法是描述這個(gè)集合的一種方法。形式文法之所以這樣命名，是因?yàn)樗c人類自然語(yǔ)言中的文法相似的緣故。

形式文法描述形式語(yǔ)言的基本想法是，從一個(gè)特殊的初始符號(hào)出發(fā)，不斷的應(yīng)用一些產(chǎn)生式規(guī)則，從而生成出一個(gè)字串的集合。產(chǎn)生式規(guī)則指定了某些符號(hào)組合如何被另外一些符號(hào)組合替換。

最常見(jiàn)的文法的分類系統(tǒng)是諾姆·喬姆斯基于1956年發(fā)展的喬姆斯基譜系，這個(gè)分類譜系把所有的文法分成四種類型：無(wú)限制文法、上下文相關(guān)文法、上下文無(wú)關(guān)文法和正規(guī)文法。四類文法對(duì)應(yīng)的語(yǔ)言類分別是遞歸可枚舉語(yǔ)言、上下文相關(guān)語(yǔ)言、上下文無(wú)關(guān)語(yǔ)言和正規(guī)語(yǔ)言。1

本詞條內(nèi)容貢獻(xiàn)者為:

楊明 - 副教授 - 西南大學(xué)