理論電腦科學中,帕里克定理指出,對於上下文無關語言,如果只關心其中每個終止符號出現的次數,而不考慮它們的順序,那麼存在正規語言與其對應[1]。這個定理可用於確定具有給定數量終止符號的字串是否能為上下文無關語法接受[2]。1961年羅希特·帕里克第一次證明了它[3],論文於1966年再次發表[4]

定義及形式化表述

編輯

 為一個字母。定義單詞的帕里克向量 為函式[1]

 ,其中 表示詞  出現的次數。

一個子集 線性的,如果它形如

存在向量 ,使得 

一個子集 半線性的,如果它為有限多線性子集的並。

帕里克定理的形式化表述如下。令 為上下文無關語言。令  單詞的帕里克向量集,即 。則 是半線性的。

兩種語言可以等效互換,如果他們的帕里克向量集相同。若 為任意半線性集,則對單詞的帕里克向量位於 中的語言,可等效於某些正規語言。因此,每一個上下文無關語言都可等效於某些正規語言。

重要性

編輯

帕里克定理表明,有些上下文無關語言可能只有歧義語法[需要更深入解釋]。這樣的語言稱為原生歧義語言。從形式文法的角度看,這意味著某些有歧義的上下文無關文法無法轉換為明確的上下文無關文法。

參考文獻

編輯
  1. ^ 1.0 1.1 Kozen, Dexter. Automata and Computability. New York: Springer-Verlag. 1997. ISBN 3-540-78105-6. 
  2. ^ Håkan Lindqvist. Parikh's theorem (PDF). Umeå Universitet. [2017-08-25]. (原始內容 (PDF)存檔於2021-05-06). 
  3. ^ Parikh, Rohit. Language Generating Devices. Quartly Progress Report, Research Laboratory of Electronics, MIT. 1961. 
  4. ^ Parikh, Rohit. On Context-Free Languages. Journal of the Association for Computing Machinery. 1966, 13 (4).