正规文法(四元式)定义了某种正规语言,正规式表示了某个正规集,它也定义了某种正规语言,因此可以说正规式和正规文法是等价的。...② 正规式转换为正规文法
将正规式 r 转换为正规文法 G,核心是将正规式拆分为正规文法的多个产生式,这是一个由一到多的过程。...可能会有下面这种写法:
S → R → (ab|a)* → (ab|a)*ε
S → (ab|a)S,S → ε
S → AS,A → (ab|a),S → ε
S → AS,A → ab,A → a,...S → ε
S → AS,A → aB,B → b,A → a,S → ε
这种写法是错误的,因为它没有严格按照规则进行转化。...正确写法如下:
S → R → (ab|a)* → (ab|a)*ε
S → (ab|a)S,S → ε
S → abS,S → aS,S → ε
S → aA,A → bS,S → aS,S → ε