前綴文法
在計算機科學中，前綴文法是類似形式文法的一種文法，這裏的字符串是從基礎字符串通過不斷的替代前綴建造出來的。前綴文法精確的描述了所有正則語言。
形式定義
[編輯]前綴文法 G 是3-元組 (Σ, S, P)，這裏的
- Σ 是有限字母表
- S 是在 Σ 上的基礎字符串的有限集合
- P 是形如 u → v 的產生規則的集合，u 和 v 是 Σ 上的字符串
每個產生式 u → v 只可以應用於形如 uw 的字符串。
例子
[編輯]一個簡單的例子前綴文法可以定義為
- Σ = {0, 1}
- S = {01, 10}
- P = {0 → 010, 10 → 100}
它描述如下正則表達式所定義的語言
性質
[編輯]前綴文法生成前綴閉合的語言。