查看“︁帕里克定理”︁的源代码

{{noteTA
|G1=IT
}}
在[[理論計算機科學]]中，'''帕里克定理'''指出，对于[[上下文无关语言]]，如果只关心其中每个[[上下文无关文法|终止符号]]出现的次数，而不考虑它们的顺序，那么存在[[正则语言]]与其对应<ref name="kozen">{{Cite book|title=Automata and Computability|last=Kozen|first=Dexter|publisher=Springer-Verlag|year=1997|isbn=3-540-78105-6|location=New York}}</ref>。这个定理可用于确定具有给定数量终止符号的字符串是否能为上下文无关语法接受<ref>{{cite web|url=http://www8.cs.umu.se/kurser/TDBC92/VT06/final/3.pdf|title=Parikh's theorem|author=Håkan Lindqvist|publisher=Umeå Universitet|access-date=2017-08-25|archive-date=2021-05-06|archive-url=https://web.archive.org/web/20210506235450/http://www8.cs.umu.se/kurser/TDBC92/VT06/final/3.pdf}}</ref>。1961年[[Rohit Jivanlal Parikh|罗希特·帕里克]]第一次证明了它<ref>{{Cite journal|title=Language Generating Devices|last=Parikh|first=Rohit|authorlink=Rohit Jivanlal Parikh|journal=Quartly Progress Report, Research Laboratory of Electronics, MIT|year=1961}}</ref>，论文于1966年再次发表<ref>{{cite journal |last1=Parikh |first1=Rohit|authorlink=Rohit Jivanlal Parikh|year=1966 |title=On Context-Free Languages|journal=Journal of the [[Association for Computing Machinery]]|volume=13|issue=4|url=http://portal.acm.org/citation.cfm?id=321364&dl=}}</ref>。

== 定义及形式化表述 ==
令<math>\Sigma=\{a_1,a_2,\ldots,a_k\}</math>为一个[[字母系統|字母]]。定义单词的''帕里克矢量''<math>p:\Sigma^*\to\mathbb{N}^k</math>为函数<ref name="kozen"/>

<math>p(w)=(|w|_{a_1}, |w|_{a_2}, \ldots, |w|_{a_k})</math>，其中<math>|w|_{a_i}</math>表示词<math>w</math>中<math>a_i</math>出现的次数。

一个子集<math>\mathbb{N}^k</math>是''线性''的，如果它形如

存在向量<math>u_0,\ldots,u_m</math>，使得<math>u_0+\langle u_1,\ldots,u_m\rangle=\{u_0+t_1u_1+\ldots+t_mu_m \mid t_1,\ldots,t_m\in\mathbb{N}\}</math>。

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

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

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

== 重要性 ==
帕里克定理表明，有些上下文无关语言可能只有[[歧义语法]]{{explain|reason=为什么？|date=2017年4月}}。这样的语言称为''[[固有歧义语言]]''。从[[形式文法]]的角度看，这意味着某些有歧义的[[上下文无关文法]]无法转换为明确的上下文无关文法。

== 参考文献 ==
{{reflist}}

[[Category:形式语言]]