帕里克定理

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

定義及形式化表述

令$\Sigma =\{a_{1},a_{2},\ldots ,a_{k}\}$為一個字母。定義單詞的帕里克矢量$p:\Sigma ^{*}\to \mathbb {N} ^{k}$為函數

$p(w)=(|w|_{a_{1}},|w|_{a_{2}},\ldots ,|w|_{a_{k}})$，其中$|w|_{a_{i}}$表示詞$w$中$a_{i}$出現的次數。

一個子集$\mathbb {N} ^{k}$是線性的，如果它形如

存在向量$u_{0},\ldots ,u_{m}$，使得$u_{0}+\langle u_{1},\ldots ,u_{m}\rangle =\{u_{0}+t_{1}u_{1}+\ldots +t_{m}u_{m}\mid t_{1},\ldots ,t_{m}\in \mathbb {N} \}$。

一個子集$\mathbb {N} ^{k}$是半線性的，如果它為有限多線性子集的並。

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

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

重要性

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