Question

请教高人 编译原理--正规文法

一道搞的我头大的题目：
用语言描述所有以0开始以1结尾的二进制序列,然后用把该语言转换为正规文法.

我写的语言：
L(G)={ 0m1n | m,n>0 }
(m和n是幂的意思,没办法写到上面,大家凑合着看一下吧)

我转换的正规文法:
S->0S|0A
A->0S|1A|0B|1
B->1A

我感觉这个文法写的不是很地道,好象多了很多不必要的东西,还请高手赐教,谢谢
最后一个产生式少了一点,应该是
B->1A|1
我认为如果去掉B的话就没办法识别类似010101的序列,不知道有没有朋友能有更好的文法,谢谢

Answer 1

S->1A

A->1A|0B

B->0B|ε

这是我的答案，可以参考