Регулярное выражение для строк битов с четным числом 1 с
Позволить L= { w in (0+1)* | w has even number of 1s}, т.е. L является набором всех строк битов с четным числом 1 с. Какое из регулярных выражений ниже представляет L?
A) (0*10*1) *
B) 0* (10*10*)*
C) 0* (10*1) * 0*
D) 0*1 (10*1) * 10*
Согласно мне опция D никогда не корректно, потому что это не представляет строку битов с нулем 1 s. Но что относительно других опций? Мы обеспокоены числом 1 с (даже или не) не, количество нулей не имеет значения.
Затем, который является корректной опцией и почему?
6 ответов
A, если неверно. Ему не соответствует 0110 (или любая непустая строка, состоящая только из нулей)
B означает ОК. Я не буду здесь доказывать это, поскольку поля страницы слишком малы.
C не соответствует 010101010 (ноль в середине не совпадает)
D, как вы сказали, не соответствует 00 или любому другому # без каких-либо единиц.
Так что только B
Чтобы решить такую проблему, вы должны
- предоставить шаблоны контрпримеров для всех "неправильных" регулярных выражений. Это будет либо неподходящая строка в
L, либо соответствующая строка изL. Чтобы доказать оставшийся «правильный» шаблон, вы должны ответить на два вопроса:
- Каждая ли строка, которая соответствует шаблону, принадлежит
L? Это можно сделать, разработав свойства, которым должна удовлетворять каждая из совпадающих строк - например, количество вхождений некоторого символа ... - Соответствует ли каждая строка в
Lрегулярному выражению? Это делается путем разделенияLна легко анализируемые подклассы и демонстрации того, что каждый из них по-своему соответствует шаблону.
- Каждая ли строка, которая соответствует шаблону, принадлежит
(Нет конкретных ответов из-за [домашнего задания]).
Изучение шаблона 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 s.
Ищите примеры, которые должны совпадать, но не т. 0 , 11011 и 1100 должны все совпадать, но каждый из них не соответствует одному из этих четырех
быстрый скрипт 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
C некорректен, поскольку не допускает 0 между вторым 1 одной группы и первым 1 следующей группы.