跳至內容

帕里克定理

本頁使用了標題或全文手工轉換
維基百科,自由的百科全書

理論電腦科學中,帕里克定理指出,對於上下文無關語言,如果只關心其中每個終止符號出現的次數,而不考慮它們的順序,那麼存在正則語言與其對應[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).