正規文法

正規文法是左線性文法和右線性文法的統稱。它們都是Chomsky分類下的3型文法。由正規文法產生的語言稱為正規集。下面我們將會看到，這裡之所以用“正規”二字為一種語言命名，是因為這種語言的結構可以用所謂正規式來描述。

基本介紹

• 中文名：正規文法
• 分類：左線性文法和右線性文法
• 類型：Chomsky
• 結構：正規式

1．右線性文法

設G[S]=(VN，VT，P，S)為CFG，若P中的產生式均有如下的形式：

A→aB或A→a（A∈VN，a∈VT+）

則稱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},

是正規文法