帕里克定理

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

令${\displaystyle \mathrm{\Sigma <!--\; \Sigma \; -->}=\{a_1,a_2,\dots <!--\; \dots \; -->,a_k\}}$${\displaystyle p:{\mathrm{\Sigma <!--\; \Sigma \; -->}}^{\ast <!--\; \ast \; -->}\to <!--\; \to \; -->{\mathbb{N}}^k}$的，如果它形如

存在向量${\displaystyle u_0,\dots <!--\; \dots \; -->,u_m}$，如果它为有限多线性子集的并。

帕里克定理的形式化表述如下。令${\displaystyle L}$，如果他们的帕里克矢量集相同。若${\displaystyle S}$。从形式文法的角度看，这意味着某些有歧义的上下文无关文法无法转换为明确的上下文无关文法。