前綴文法

在計算機科學中，前綴文法是類似形式文法的一種文法，這裡的字元串是從基礎字元串通過不斷的替代前綴建造出來的。前綴文法精確的描述了所有正則語言。

基本介紹

• 中文名：前綴文法
• 學科：計算機科學

形式定義

前綴文法G是3-元組(Σ,S,P)，這裡的

• Σ 是有限字母表
  
• S是在 Σ 上的基礎字元串的有限集合
  
• P是形如u→v的產生規則的集合，u和v是 Σ 上的字元串
  

每個產生式u→v只可以套用於形如uw的字元串。

例子

一個簡單的例子前綴文法可以定義為

• Σ = {0, 1}
  
• S= {01, 10}
  
• P= {0 → 010, 10 → 100}
  

它描述如下正則表達式所定義的語言

性質

前綴文法生成前綴閉合的語言。

正則語言

正則語言又稱正規語言是滿足下述相互等價的一組條件的一類形式語言：

• 可以被確定有限狀態自動機識別；
  
• 可以被非確定有限狀態自動機識別；
  
• 可以被唯讀圖靈機識別；
  
• 可以用正則表達式描述；
  
• 可以用正則文法生成。
  
• 可以用前綴文法生成。