Кратчайшее регулярное выражение для двоичного числа с четным числом нулей или нечетным числом единиц

Напишите выражение, содержащее четное количество нулей или нечетное количество единиц.

Я понял:

1*(01*01*)* + 0*10*(10*10*)*

где первая часть представляет собой четное количество нулей, а вторая часть - нечетное количество единиц.

Однако должно быть упрощенное решение, которого я не вижу. Какие-нибудь советы?


regex regular-language finite-automata
person user3085290    schedule 10.12.2013    source источник
comment
Какой язык программирования использует + для альтернатив в регулярном выражении? Насколько я знаю, это используется только в теории автоматов, а не при программировании.   -  person Barmar    schedule 10.12.2013
comment
Почему не substr_count()?   -  person Petah    schedule 10.12.2013
comment
Упс, может не тот тэг поставил. Извини   -  person user3085290    schedule 10.12.2013
comment
домашнее задание да? РЖУ НЕ МОГУ   -  person jondinham    schedule 10.12.2013
comment
Я попробовал это на regexpal.com, и, похоже, это сработало: ^(1(11)*|(00)+)$   -  person bdean20    schedule 10.12.2013
comment
Есть советы? -- Узнайте из этого ответа Как написать регулярное выражение для DFA, используя теорему Ардена Обратите внимание, что конечное состояние для вас — Q3.   -  person Grijesh Chauhan    schedule 10.12.2013
comment
Кстати, ваш RE неверен, вам не хватает многих строк   -  person Grijesh Chauhan    schedule 10.12.2013
comment
@Barmar В теории автоматов + в качестве бинарного оператора используется Union, и если он появляется в форме надстрочного индекса как унарный оператор, это означает повторение один или несколько раз.   -  person Grijesh Chauhan    schedule 10.12.2013
comment
Может быть, обнаружить случай сбоя? (нечетное количество 0 и четное количество 1)   -  person Julián Urbano    schedule 10.12.2013
comment
Я только что написал регулярное выражение с нуля OP и придумал регулярное выражение точно такой же длины, как у вас (и на 95% идентично). Я намеренно не прочитал ваше сначала, поэтому я подозреваю, что может не быть более короткого выражения.   -  person OGHaza    schedule 19.12.2013
comment
Я согласен с @OGHaza, что условия базового состояния не допускают меньшего количества состояний.   -  person gtgaxiola    schedule 19.12.2013
comment
Проверьте мой обновленный ответ. 0*1(0|10*1)* — еще более короткое регулярное выражение для части с нечетными единицами   -  person Julián Urbano    schedule 19.12.2013
comment
@ user3085290 Вам нужно четное количество нулей и нечетное количество единиц или четное количество нулей или нечетное количество единиц?   -  person The Guy with The Hat    schedule 21.12.2013

Ответы (6)


arrow_upward
19
arrow_downward

Часть нечетных единиц: 0*1(0|10*1)*

Часть с четными нулями зависит:

  1. Пустая строка верна: (1|01*0)*
  2. Нет-0 с четными-0 с: (1|01*0)+
  3. Должно быть не менее двух нулей: 1*(01*01*)+ (как в OP)

старый ответ: правильный в случаях 1 и 2

(1*(01*0)*)+ | 0*1(0*(10*1)*)*

Спасибо @OGHaza за полезные комментарии.

person Julián Urbano    schedule 10.12.2013
comment
пример несовпадающей строки с нечетным количеством единиц - person OGHaza; 19.12.2013
comment
@OGHaza, ты прав, там было + вместо *, спасибо! regexr.com?37nfq - person Julián Urbano; 19.12.2013
comment
Кажется, он не соответствует пустой строке (ноль 0s все еще четный). Однако это легко исправить: замените любой или оба + на *. - person DPenner1; 19.12.2013
comment
@DPenner да, я намеренно заставляю его быть непустым - person Julián Urbano; 19.12.2013
comment
Ну, вы побрили 4 символа из регулярного выражения OP, и я думаю, что вы зашли так далеко, как только могли;) +1 - person OGHaza; 19.12.2013
comment
Это то, что можно подумать... пока не появится кто-то другой :-) - person Julián Urbano; 19.12.2013
comment
Ваш ответ неверен, так как также возможно сгенерировать неверную строку из вашего RE (1*(01*0)*)+ использовать для записи 111010, которая неверна. Вы можете проверить этот ответ: Требуется регулярное выражение для конечных автоматов: четное количество единиц и четное количество нулей - person Grijesh Chauhan; 23.12.2013
comment
@GrjeshChauhan правильно, потому что у него два нуля. Это четные 0 или нечетные 1 - person Julián Urbano; 23.12.2013
comment
@GrjeshChauhan, разве 2-я и 3-я части не излишние? Кроме того, они не заставляют нечетное количество единиц. Они заставляют по крайней мере одного, но их может быть сколько угодно. - person Julián Urbano; 23.12.2013
comment
Да правильно (1*01*01*)* + (0*10*10*)*10* + 0*1(0*10*10*)* по ошибке я добавил * в 1 - person Grijesh Chauhan; 23.12.2013
comment
@GrjeshChauhan заставляют хотя бы один 0 (в скобках). Опять же, 2-я и 3-я часть избыточны, верно? (давайте удалим старые комментарии, чтобы они не разрастались слишком долго) - person Julián Urbano; 23.12.2013
comment
Да я еще раз проверил и теперь думаю последние двое раскаиваются. Можем убрать любую. - person Grijesh Chauhan; 23.12.2013

arrow_upward
11
arrow_downward

Используя тот факт, что строки четной длины ВСЕГДА удовлетворяют вашим ограничениям:

^(([01]{2})*|1*(01*01*)*)$
person Ruud Helderman    schedule 24.12.2013
comment
Здесь используется столько же символов, сколько и в моем регулярном выражении, но я думаю, что очень хороший улов о строках четной длины заслуживает этой награды. Обратите внимание, что это регулярное выражение не требует случая 0s-is-even-0s. - person Julián Urbano; 25.12.2013
comment
Было бы короче, если бы 1*(01*01*)* был заменен на (1|01*0)* (как в решении @JuliánUrbano). Но да, очень умно, +1! - person Volatility; 25.12.2013
comment
и, что еще более важно... кратчайшее время выполнения! - person gillyspy; 28.12.2013

arrow_upward
1
arrow_downward

Определите кратчайший. Если вы ищете кратчайшее время оценки (то есть самое быстрое), убедитесь, что вы не используете группы захвата.

вот пример в javascript

^(?:1*(?:01*0)*)+|0*1(?:0*(?:10*1)*)*$

которое показывает на 20% быстрее, чем это выражение, которое использует группы захвата, но даст вам тот же ответ

^(1*(01*0)*)+|0*1(0*(10*1)*)*$
person gillyspy    schedule 24.12.2013
comment
Я имею в виду самый короткий, как в наименьшем количестве символов. В конце концов, группы без захвата — это просто сахар, зависящий от языка. - person Julián Urbano; 24.12.2013
comment
да, я думаю, мы знаем, что вы хотели @JuliánUrbano. Так что мой вопрос к оп. Ты тоже не ОП? Но для вас, Джулиан... интересно, в каких практических сценариях вы (конкретно вы, не генерал, вы) предпочли бы самую короткую длину выражения, а не самое короткое время оценки? - person gillyspy; 24.12.2013
comment
щедрость просто для удовольствия, чтобы увидеть, есть ли что-то короче - person Julián Urbano; 24.12.2013
comment
ваш комментарий появился до того, как я сохранил свой вопрос, чтобы уточнить: так что никакой практической цели, просто для удовольствия? Кроме того, можем ли мы получить подтверждение того, что вы и оператор имеете в виду короче таким же образом? И кто так или иначе голосует за меня, есть ли какой-то способ, которым мой ответ / комментарии не имеют отношения к информации, которую мы предоставили? - person gillyspy; 24.12.2013

arrow_upward
0
arrow_downward

Наиболее упрощенное решение, которое я нашел, это:

1+0(0+1)((1+0)(1+0))*
person Mehran    schedule 25.01.2015

arrow_upward
0
arrow_downward

как насчет этого выражения:

(1(11)*+(00)*)

person khalid J-A    schedule 20.03.2021

arrow_upward
0
arrow_downward

С наименьшим количеством символов,

1*(01*01*)*
person Moses Kirathe    schedule 05.03.2018