正则表达式,描述{0,1}的语言,没有交替的0

Question

它主要在标题中,我的意思是交替是在两次出现的0之间存在单个1或0.所以不会出现0 1 0或0 0 0.

我试图理解问题的理论性质,所以我更喜欢连接,连接和闭包(10,1 | 0和10*).

请注意,这不是一个我只对这个问题感兴趣的作业问题,所以请不要光顾那些影响的评论.

编辑:从"之间的第一款改变了措辞的出现"到"之间的2出现".

Answer 1

第一个重要的观察是我们可以减少问题:如果S被允许并且1以两个为结尾,则S允许与任何允许的序列连接.那么什么使得有效的S？

1. 1在S中显式,并且任何多于一个的序列1将始终11以S 结尾,因此在S中.
2. A 01可能只会跟随另一个1,就像0给出的那样010.这结束了11,有效的S.
3. A 00只能跟随11,as 0000,0001并且0010所有都具有交替的零.这结束了11,有效的S.

所以这告诉我们任何S匹配^(1|011|0011)*$.但是我们没有完成,因为有一些其他序列对S无效但是它们本身是允许的序列,因此可以连接到S.

• 0
• 00
• 01
• 001

000 当然是不允许的,任何更长的要么是在S中,要么本身是不允许的.

因此,整个正则表达式匹配允许的序列是:

^(1|011|0011)*(|0|00|01|001)$

这是零个或多个S序列,任选地随后是我们允许的非S序列之一.