Регулярное выражение для битовых строк с четным числом 1 с

Question

Пусть L= { w in (0+1)* | w has even number of 1s}, т. Е. L - набор всех битовых строк с четным числом 1 с. Какое из приведенных ниже регулярных выражений представляет собой L?

А) (0 * 10 * 1) *
Б) 0 * (10 * 10 *) *
В) 0 * (10 * 1) * 0 *
D) 0 * 1 (10 * 1) * 10 *

По моему мнению, опция D никогда не верна, потому что она не представляет битовую строку с нулем 1 с. Но как насчет других вариантов? Нас беспокоит количество единиц (даже или нет), а не количество нулей не имеет значения.

Тогда какой правильный вариант и почему?

Answer 1

A, если false. Это не соответствует 0110 (или любой непустой строке только для нулей)

B означает ОК. Я не буду доказывать это здесь, поскольку поля страницы слишком малы.

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*10*10*)

Answer 5

быстрый скрипт на 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
• удалено, потому что оно соответствует 1
• удалено b, потому что соответствует 10

Answer 6

C неверно, поскольку не допускает никаких нулей между вторым 1 в одной группе и первым 1 в следующей группе.

Answer 7

Ищите примеры, которые должны соответствовать, но не совпадают. 0, 11011 и 1100 должны совпадать, но каждый из них не подходит для одного из этих четырех