Пусть L= { w in (0+1)* | w has even number of 1s}, т.е. L - это набор всех битовых строк с четным числом 1s. Какое из регулярных выражений ниже представляет L?
A) (0 * 10 * 1) *
B) 0 * (10 * 10 *) *
C) 0 * (10 * 1) * 0 *
D) 0 * 1 (10 * 1) * 10 *
В соответствии со мной опция D никогда не верна, потому что она не представляет битовую строку с нулевым значением 1 с. Но как насчет других вариантов? Мы обеспокоены количеством 1s (даже или нет), а не количеством нулей не имеет значения.
Тогда это правильный вариант и почему?
A, если false. Это не соответствует 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.
Посмотрите примеры, которые должны совпадать, но не нужно. 0, 11011 и 1100 должны совпадать, но каждый из них не подходит для одного из четырех
C неверен, потому что он не допускает никаких 0s между вторым 1 из одной группы и первым 1 следующей группы.
Этот ответ был бы лучшим для этого языка
(0*10*10*)
быстрый python script фактически устранил все возможности:
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)
вывод: