-
正規文法
鎖定
- 中文名
- 正規文法
- 外文名
- Regular Grammar
- 別 名
- 3型文法
- 分 類
- 左線性文法和右線性文法
- 結 構
- 正規式
分類
1.右線性文法
設G[S]=(VN,VT,P,S)為CFG,若P中的產生式均有如下的形式:
則稱G為右線性文法。例如,文法
G1[S]=({S,A,B},{a,b},P1,S)
其中
P1={S→aA,A→aA,A→bB,A→b,B→bB,B→b}
為一右線性文法,G1所產生的正規集為
L(G1)={aibj |i,j≥1}
2.左線性文法
若一個文法G[S]=(VN,VT,P,S)中的產生式均有如下的形式:
A→Ba或A→a(A,B∈VN,a∈VT+)
則稱G為左線性文法。例如,文法
G2[S]=({S,A},{a,b},P2,S)
其中
P2={S→Sb,S→Ab,A→Aa,A→a}
為一左線性文法,且有
L(G2)=L(G1)={aibj |i,j≥1}
請注意,雖然文法
G3[S]=({S,A,B},{a,b},P3,S)
其中
P3={S→aA,A→aA,A→Bb,A→b,B→Bb,B→b}
也同樣產生語言{aibj |i,j≥1},但由於G3中同時含有左線性產生式和右線性產生式,故G3不是正規文法。
另外
P4={S-->aA,A-->ab},
是正規文法
- 詞條統計
-
- 瀏覽次數:次
- 編輯次數:17次歷史版本
- 最近更新: 飞熊李李