前綴文法
前綴文法
前綴文法G是3-元組，這裡的
• Σ 是有限字母表
• S是在 Σ 上的基礎字元串的有限集合
• P是形如的產生規則的集合，u和v是 Σ 上的字元串
每個產生式 只可以應用於形如 的字元串。
一個簡單的例子前綴文法可以定義為
•
•
•
它描述如下正則表達式所定義的語言
前綴文法生成前綴閉合的語言。
正則語言又稱 正規語言是滿足下述相互等價的一組條件的一類形式語言：
• 可以被確定有限狀態自動機識別；
• 可以被非確定有限狀態自動機識別；
• 可以被只讀圖靈機識別；
• 可以用正則表達式描述；
• 可以用正則文法生成。
• 可以用前綴文法生成。