帕里克定理[编辑]
外观
在理论计算机科学中,帕里克定理指出,对于上下文无关语言,如果只关心其中每个终止符号出现的次数,而不考虑它们的顺序,那么存在正则语言与其对应[1]。这个定理可用于确定具有给定数量终止符号的字符串是否能为上下文无关语法接受[2]。1961年罗希特·帕里克第一次证明了它[3],论文于1966年再次发表[4]。
定义及形式化表述
[编辑],其中表示词中出现的次数。
一个子集是线性的,如果它形如
存在向量,使得。
一个子集是半线性的,如果它为有限多线性子集的并。
帕里克定理的形式化表述如下。令为上下文无关语言。令为单词的帕里克矢量集,即。则是半线性的。
两种语言可以等效互换,如果他们的帕里克矢量集相同。若为任意半线性集,则对单词的帕里克矢量位于中的语言,可等效于某些正则语言。因此,每一个上下文无关语言都可等效于某些正则语言。
重要性
[编辑]帕里克定理表明,有些上下文无关语言可能只有歧义语法[需要更深入解释]。这样的语言称为固有歧义语言。从形式文法的角度看,这意味着某些有歧义的上下文无关文法无法转换为明确的上下文无关文法。
参考文献
[编辑]- ^ 跳转到: 1.0 1.1 Kozen, Dexter. Automata and Computability. New York: Springer-Verlag. 1997. ISBN 3-540-78105-6.
- ^ Håkan Lindqvist. Parikh's theorem (PDF). Umeå Universitet. [2017-08-25]. (原始内容 (PDF)存档于2021-05-06).
- ^ Parikh, Rohit. Language Generating Devices. Quartly Progress Report, Research Laboratory of Electronics, MIT. 1961.
- ^ Parikh, Rohit. On Context-Free Languages. Journal of the Association for Computing Machinery. 1966, 13 (4).