帕里克定理

Template:NoteTA 在理論計算機科學中，帕里克定理指出，对于上下文无关语言，如果只关心其中每个终止符号出现的次数，而不考虑它们的顺序，那么存在正则语言与其对应。这个定理可用于确定具有给定数量终止符号的字符串是否能为上下文无关语法接受。1961年罗希特·帕里克第一次证明了它，论文于1966年再次发表。

定义及形式化表述

令$\mathrm{\Sigma }=\{a_1,a_2,\dots ,a_k\}$为一个字母。定义单词的帕里克矢量$p:{\mathrm{\Sigma }}^{*}\to {\mathbb{N}}^k$为函数

$p(w)=(|w{|}_{a_1},|w{|}_{a_2},\dots ,|w{|}_{a_k})$，其中$|w{|}_{a_i}$表示词$w$中$a_i$出现的次数。

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

存在向量$u_0,\dots ,u_m$，使得$u_0+⟨u_1,\dots ,u_m⟩=\{u_0+t_1{u}_1+\dots +t_m{u}_m\mid t_1,\dots ,t_m\in \mathbb{N}\}$。

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

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

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

重要性

帕里克定理表明，有些上下文无关语言可能只有歧义语法Template:Explain。这样的语言称为固有歧义语言。从形式文法的角度看，这意味着某些有歧义的上下文无关文法无法转换为明确的上下文无关文法。