帕里克定理

令${\displaystyle \Sigma =\{a_{1},a_{2},\ldots ,a_{k}\}}$ 为一个字母。定义单词的帕里克矢量${\displaystyle p:\Sigma ^{*}\to \mathbb {N} ^{k}}$ 为函数^[1]

${\displaystyle p(w)=(|w|_{a_{1}},|w|_{a_{2}},\ldots ,|w|_{a_{k}})}$ ，其中${\displaystyle |w|_{a_{i}}}$ 表示词${\displaystyle w}$ 中${\displaystyle a_{i}}$ 出现的次数。

一个子集${\displaystyle \mathbb {N} ^{k}}$ 是线性的，如果它形如

存在向量${\displaystyle u_{0},\ldots ,u_{m}}$ ，使得${\displaystyle 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} \}}$ 。

一个子集${\displaystyle \mathbb {N} ^{k}}$ 是半线性的，如果它为有限多线性子集的并。

帕里克定理的形式化表述如下。令${\displaystyle L}$ 为上下文无关语言。令${\displaystyle P(L)}$ 为${\displaystyle L}$ 单词的帕里克矢量集，即${\displaystyle P(L)=\{p(w)\mid w\in L\}}$ 。则${\displaystyle P(L)}$ 是半线性的。

两种语言可以等效互换，如果他们的帕里克矢量集相同。若${\displaystyle S}$ 为任意半线性集，则对单词的帕里克矢量位于${\displaystyle S}$ 中的语言，可等效于某些正则语言。因此，每一个上下文无关语言都可等效于某些正则语言。

帕里克定理表明，有些上下文无关语言可能只有歧义语法^{[需要进一步解释]}。这样的语言称为固有歧义语言。从形式文法的角度看，这意味着某些有歧义的上下文无关文法无法转换为明确的上下文无关文法。