帕里克定理

在理論計算機科學中，帕里克定理指出，對於上下文無關語言，如果只關心其中每個終止符號出現的次數，而不考慮它們的順序，那么存在正則語言與其對應。這個定理可用於確定具有給定數量終止符號的字元串是否能為上下文無關語法接受。1961年羅希特·帕里克第一次證明了它，論文於1966年再次發表。

基本介紹

• 中文名：帕里克定理
• 學科：計算機

定義及形式化表述

令為一個字母。定義單詞的帕里克矢量為函式

，其中表示詞w中出現的次數。

一個子集是線性的，如果它形如

存在向量，使得。

一個子集是半線性的，如果它為有限多線性子集的並。

帕里克定理的形式化表述如下。令L為上下文無關語言。令 P(L)為L單詞的帕里克矢量集，即。則P(L)是半線性的。

兩種語言可以等效互換，如果他們的帕里克矢量集相同。若S為任意半線性集，則對單詞的帕里克矢量位於S中的語言，可等效於某些正則語言。因此，每一個上下文無關語言都可等效於某些正則語言。

重要性

帕里克定理表明，有些上下文無關語言可能只有歧義語法Template:Explain。這樣的語言稱為固有歧義語言。從形式文法的角度看，這意味著某些有歧義的上下文無關文法無法轉換為明確的上下文無關文法。

上下文無關文法

在計算機科學中，形式語言是：某個字母表上，一些有限長字串的集合，而形式文法是描述這個集合的一種方法。形式文法之所以這樣命名，是因為它與人類自然語言中的文法相似的緣故。

形式文法描述形式語言的基本想法是，從一個特殊的初始符號出發，不斷的套用一些產生式規則，從而生成出一個字串的集合。產生式規則指定了某些符號組合如何被另外一些符號組合替換。

最常見的文法的分類系統是諾姆·喬姆斯基於1956年發展的喬姆斯基譜系，這個分類譜系把所有的文法分成四種類型：無限制文法、上下文相關文法、上下文無關文法和正規文法。四類文法對應的語言類分別是遞歸可枚舉語言、上下文相關語言、上下文無關語言和正規語言。