正规式 = 正则表达式,正规文法 = 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