正则文法查看源代码讨论查看历史

正则文法

原图链接来自 搜狗 的图片

正规文法是左线性文法和右线性文法的统称。它们都是Chomsky分类下的3型文法。由正规文法产生的语言称为正规集。下面我们将会看到，这里之所以用“正规”二字为一种语言命名，是因为这种语言的结构可以用所谓正规式来描述。

目录

基本内容

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

也不是正规文法