跳至內容

前綴文法

維基百科,自由的百科全書

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

形式定義

前綴文法 G3-元組 (Σ, S, P),這裏的

  • Σ 是有限字母表
  • S 是在 Σ 上的基礎字符串的有限集合
  • P 是形如 uv產生規則的集合,uv 是 Σ 上的字符串

每個產生式 uv 只可以應用於形如 uw 的字符串。

例子

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

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

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

性質

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

參見