偶数个 1 的位串的正则表达式

Question

设 L= { w in (0+1)* | w有偶数个1}，即L是所有有偶数个1的比特串的集合。下面哪一个正则表达式代表 L？

A) (0*10*1)*
B) 0*(10*10*)*
C) 0*(10*1)* 0*
D) 0*1(10*1)* 10*

根据我的说法，选项 D 永远不会正确，因为它不代表零个 1 的位串。但其他选择又如何呢？我们关心的是 1 的数量（偶数与否），而不是 0 的数量。

那么哪个是正确的选项，为什么？

Answer 1

A 如果为假。它不会与 0110（或任何仅零的非空字符串）匹配，

B 表示 OK。由于页边距太小，我不想在这里证明这一点。

C 不会与 010101010 匹配（中间的零不匹配）

D 正如你所说，不会与 00 或任何其他没有匹配的 # 匹配。

所以只有B

Answer 2

要解决此类问题，您应该

1. 为所有“不正确”的正则表达式提供反例模式。这将是 L 中不匹配的字符串，或者是 L 中的匹配字符串。

2. 为了证明剩余的“正确”模式，您应该回答两个问题：

   • 每个与模式匹配的字符串都属于L吗？这可以通过设计每个匹配字符串应满足的属性来完成 - 例如，某些字符出现的次数......
   • L 中的每个字符串都与正则表达式匹配吗？这是通过将 L 划分为易于分析的子类，并显示每个子类以自己的方式匹配模式来完成的。

（由于[家庭作业]，没有具体答案）。

Answer 3

检查模式 B：

^0*(10*10*)*$

^          # match beginning of string
0*         # match zero or more '0'
(          # start group 1
 10*       # match '1' followed by zero or more '0'
 10*       # match '1' followed by zero or more '0'
)*         # end group 1 - match zero or more times
$          # end of string

很明显，该模式只会匹配具有 0,2,4,... 1 的字符串。

Answer 4

寻找应该匹配但不匹配的示例。 0、11011 和 1100 应该全部匹配，但这四个之一都失败

Answer 5

C 是不正确的，因为它不允许一组的第二个 1 和下一组的第一个 1 之间有任何 0。

Answer 6

一个快速的Python脚本实际上消除了所有的可能性：

import re

a = re.compile("(0*10*1)*")
b = re.compile("0*(10*10*)*")
c = re.compile("0*(10*1)* 0*")
d = re.compile("0*1(10*1)* 10*")

candidates = [('a',a),('b',b),('c',c),('d',d)]
tests = ['0110', '1100', '0011', '11011']
for test in tests:
    for candidate in candidates:
        if not candidate[1].match(test):
            candidates.remove(candidate)
            print "removed %s because it failed on %s" % (candidate[0], test)

ntests = ['1', '10', '01', '010', '10101']
for test in ntests:
    for candidate in candidates:
        if candidate[1].match(test):
            candidates.remove(candidate)
            print "removed %s because it matched on %s" % (candidate[0], test)

输出：

• 删除c因为它在0110上失败
• 删除d因为它在0110上失败
• 删除a因为它在1上匹配
• 删除b因为它在10上匹配

Answer 7

这个答案最适合这种语言

(0*10*10*)