江苏龙网

  1. 首页 > 生活 > >

求0和1的个数各能被某两个数整除的正则表达式

你已经懂得如何为这种问题写DFA了，很好，然后你去看《龙书》，里面有一个DFA压缩成最精简DFA然后逆成正则表达式的算法，实现它，以后就不需要手动转换了。
■网友
这些给轮子哥点赞同的都是脑残粉吧？轮子哥答的明显不对啊，题主问能不能不通过DFA，直接构造RE，轮子哥只是告诉了一个DFA-\u0026gt;RE的算法而已，窃以为这个算法但凡学过Automata，明白RE和DFA等价性的人都应该已经知道了，题主估计也已经知道。反正我实名反对轮子哥。先占坑，下午来答。===========================更新=====================================好，我们来看这个问题，我虽然不同意轮子哥的答案，但是这是因为这答案不与问题契合，不是说这方法不给力。你必须得承认，轮子大大的思路，其实，是几乎唯一的靠谱思路，我下面会详细的说这个东西。题主的问题是【有没有什么简洁的方法可以直接构造正则表达式，而不用DFA转换？】先说个人的看法，那就是木有……因为结果就是很长很恐怖……然后从几个不同的层次和目的来看这个问题。【1】、这个题目我记得似乎是《自动机理论、语言和计算导论》的练习题，好像要求是画出DFA即可，没有要求RE。如果确实题主的意思是使用Kleene Star Notation（只有+ , ( , ) , * ）来进行表示的话，相信我吧，你的老师不会出这么浪费脑力且没有实际意义的题目的，让你去画一个(p,q)=(11,12)的DFA来转RE，这体力活太无聊了。为了让你信服这一点，我把(3,3)和(3,2)的结果放在这里供你……畏惧……一下……regex_33=\u0026#39;^((0|1(((0(01|10)(0(000)*00)?|1(000)*00)1(11(0(000)*00)?1)*1|00)0)*((0((01|10)0(000)*0|1)|1(000)*0)|(0(01|10)(0(000)*00)?|1(000)*00)1(11(0(000)*00)?1)*110(000)*0)1)((((0|1(01|10)(0(000)*00)?1)(11(0(000)*00)?1)*110(000)*0|1((01|10)0(000)*0|1))|((0|1(01|10)(0(000)*00)?1)(11(0(000)*00)?1)*1|10)0(((0(01|10)(0(000)*00)?|1(000)*00)1(11(0(000)*00)?1)*1|00)0)*((0((01|10)0(000)*0|1)|1(000)*0)|(0(01|10)(0(000)*00)?|1(000)*00)1(11(0(000)*00)?1)*110(000)*0))1)*(((0|1(01|10)(0(000)*00)?1)(11(0(000)*00)?1)*1|10)0(((0(01|10)(0(000)*00)?|1(000)*00)1(11(0(000)*00)?1)*1|00)0)*((0(01|10)(0(000)*00)?|1(000)*00)1(11(0(000)*00)?1)*(0|110(000)*1)|(0(01|10)0|1)(000)*1)|(0|1(01|10)(0(000)*00)?1)(11(0(000)*00)?1)*(0|110(000)*1)|1(01|10)0(000)*1)|1(((0(01|10)(0(000)*00)?|1(000)*00)1(11(0(000)*00)?1)*1|00)0)*((0(01|10)(0(000)*00)?|1(000)*00)1(11(0(000)*00)?1)*(0|110(000)*1)|(0(01|10)0|1)(000)*1))*$\u0026#39;regex_32=\u0026#39;^((0|1(00(1(11)*1)?0)*01)((((0|101)(11)*1|10)0(00(1(11)*1)?0)*0|1)1)*(((0|101)(11)*1|10)0(00(1(11)*1)?0)*(001(11)*0|1)|(0|101)(11)*0)|1(00(1(11)*1)?0)*(001(11)*0|1))*$\u0026#39;因为是Python里写的，我写上了边界断言^和$。实际上，我的Python只支持100个group，这两个Regex甚至都不能运行，我不得不跑到Online regex tester and debugger: JavaScript, Python, PHP, and PCRE 去测试了一下，似乎没问题，如果有游客发现问题，可以联系我，这东西不敢保证对。【2】、如果是真有无聊的作业，要进行这么无聊的体力活工作，那，你得承认这东西本来就是为了让计算机进行计算的，轮子大大的方法是几乎唯一靠谱的可以让你在短时间内写出我上面这个两个RE的方法了……我把工具放在这里，作为对轮子哥的补充~~也供你自己玩一玩。实际上各种语言造的DFA和RE的轮子还是很多的。reverie/python-automata · GitHub这是一个Python的Automata的库，你可以自己拿来玩玩，检验下自己设计的自动机效果对不对啊什么的。ferno/greenery · GitHub这是一个Python的可以解析Regex和Automata的库，支持一些自动机的交并补等等运算，可以用来互相转化，你也可以玩玩。【3】、你希望要一个常见的工程中应用的正则表达式引擎中的Regex，一个你可以自己依靠人脑短时间写出来的东西，来识别这样的语言。思路，这里重要的问题在于：1、如何计算一个串中的特定符号的数目；2、构造两个Regex的And。1是容易的，我相信你已经知道了。2也是容易的，你需要使用一个零宽正向先行断言，其实就是Non-consuming regex。(?=^(1*|01*01*0)*$)(?=^(0*|10*10*1)*$)这个短小的东东等效于上面的regex_33，你可以直接在Python里试试。这个式子是两个 (?=XXX)(?=XXX)这实际上就是两个Regex的And，至于这两个小部分，就是第1点的内容了。===============================又更===================================有人问我有没有有趣的东西看看，我就都放在这里，想起来再贴，先贴一个Matrix67的文。这文是讲匹配长度为合数的全1串的Regex的。http://www.matrix67.com/blog/archives/475


推荐阅读


上一篇：苏州it，硕士毕业两年，工资12k，在苏州是啥水平想买房，有推荐的小区吗

下一篇：网站的制作是否应该外包