求与正规式 R=0(01|10)+ 等价的正规文法

正规式 = 正则表达式,正规文法 = 3型文法

正规式转成正规文法的规则请看:将正规式转成正规文法·规则 - 简书

3型文法:产生式右端的第一个符号必须为终结符,再详细一点的介绍可以看:四种文法的类型(编译原理) - 简书


结论(不难理解):正规式a+的对应的正规文法为G[S]:S → aA | ε

开始解题:

令r = 01 | 10, 则R = 0r*, 令所求的正规文法为G[S]则有:S → 0M,M → r*, 由上述结论可直接得M → rM | ε

将r = 01 | 10回代到M中,得M → (01 | 10)M | ε, 展开后得M → 01M | 10M | 01 | 10, 将0、1开头的产生式分别合并,得M → 0(1M | 1) | 1(0M | 0)

继续转换,M → 0A | 1B, A → 1M | 1, B → 0M | 0

好了,现在所有产生式的第一个符号已经都为终结符了,也就是说,现在转换的文法已经是正规文法了。

整理得:正规式 R = 0(01 | 10)*所对应的正规文法如下:

G[S]: S → 0M

            M → rM | ε

            M → 0A | 1B

            A → 1M | 1

            B → 0M | 0

            

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。