验证用于匹配{0,1}上不含子串111的所有字符串的正则表达式是否正确

首先先把你的问题和正则贴出来：

Would the following be a correct regular expression for this?:
$$(0 + 01 + 011)^* + (0 + 10 + 110)^* + (1 \cdot (0 + 01 + 011)^) + ((0 + 10 + 110)^ \cdot 1) + 11 + 1$$

My thought process is I broke it into 4 cases (in addition to the $1$ and $11$ cases):

First case: all strings that start with 0 but end in 1
Second case: all strings that with 0 and end in 0
Third case: all strings that start with 1 and end in 1
Fourth case: all strings that start with 0 but end in 1

先提个小细节：你说的四个case里，第一和第四完全重复了（都是“以0开头、以1结尾”），应该是笔误吧？比如可能第四case是“以1开头、以0结尾”？不过咱们重点看正则本身的正确性~

先拆解你的正则各部分的作用： #

• (0 + 01 + 011)^*：这个部分是由0、01、011这三个片段任意拼接（包括拼接0次，也就是空串）生成的串。这些串的共同特点是：不会出现三个连续的1，而且每个连续的1块（1或11）前面都跟着0；同时，串的开头可以是0，结尾可以是0或1（比如0、01、011、00、001这些都能生成）。
• (0 + 10 + 110)^*：这个部分由0、10、110任意拼接生成，特点是不会出现三个连续1，且每个连续的1块后面都跟着0，所以所有生成的串都是以0结尾的（比如0、10、110、100、1010等）。
• 1 · (0 + 01 + 011)^*：开头固定是1，后面跟着第一部分的串，整体是以1开头、结尾可以是0或1的串，且全程没有三个连续1（比如1、10、101、1011等）。
• (0 + 10 + 110)^* · 1：前面是第二部分的串，末尾加一个1，生成的是结尾固定为1、开头可以是0或1的串，同样不会有三个连续1（比如01、101、1101等）。
• 单独的1和11：覆盖了长度为1和2的纯1串，这两个串本身不含111，是合法的。

验证覆盖性和正确性： #

1. 有没有遗漏合法串？
   所有不含111的二进制串，无非是这几类：

   • 空串：被前两个带*的部分覆盖（*允许0次重复）；
   • 以0开头、以0结尾：被(0 + 01 + 011)^*或(0 + 10 + 110)^*覆盖；
   • 以0开头、以1结尾：被(0 + 01 + 011)^*或(0 + 10 + 110)^* · 1覆盖；
   • 以1开头、以0结尾：被1 · (0 + 01 + 011)^*覆盖；
   • 以1开头、以1结尾：被1 · (0 + 01 + 011)^*、(0 + 10 + 110)^* · 1或者单独的1/11覆盖；
     比如像1101、1011这类边缘串，都能找到对应的部分匹配，没有遗漏。

2. 有没有匹配非法串？
   所有包含111的串，比如111、0111、1110等，都无法被你的正则匹配：

   • 前两个带*的部分要么是0开头要么是0结尾，不可能生成111；
   • 第三、第四部分要么是1开头接0相关片段，要么是0结尾片段接1，最多只会出现两个连续1；
   • 单独的1/11也和111无关；
     所以不会匹配任何含111的串。

结论 #

你的正则是正确的，完全可以匹配{0,1}上所有不含子串111的字符串！只是你的case划分有个小笔误，修正一下就更严谨啦~

备注：内容来源于stack exchange，提问作者Omaro_IB