Регулярное выражение, которое описывает язык {0,1} без чередующихся 0

Question

Это в основном в названии, что я имею в виду под чередованием того, что между двумя вхождениями 0 стоит один или 0.Так что нет таких случаев 0 1 0 или 0 0 0 .

Я пытаюсь понять теоретическоехарактер вопроса, поэтому я бы предпочел ответ с точки зрения только конкатенации, объединения и замыкания (10, 1 | 0 и 10 *).

Обратите внимание, что это НЕ aВопрос по домашнему заданию Меня просто интересует вопрос, поэтому, пожалуйста, не делайте покровительственных комментариев по этому поводу.

Редактировать: изменил формулировку в первом абзаце с "между вхождениями " на "между два вхождения ".

Answer 1

Первое важное наблюдение заключается в том, что мы можем уменьшить проблему: если S разрешен и равен 1 или заканчивается двумя, то S, сцепленный с любой разрешенной последовательностью, остается разрешенным. Так что же делает действительный S?

1. 1 явно в S, и любая последовательность из более чем одного 1 всегда будет заканчиваться 11, как и в S.
2. За 01 может следовать только другой 1, так как 0 даст 010. Это заканчивается на 11, и поэтому является действительным S.
3. A 00 может сопровождаться только 11, поскольку 0000, 0001 и 0010 все имеют чередующиеся нули. Это заканчивается на 11, и поэтому является действительным S.

Так что это говорит нам о любых S совпадениях ^(1|011|0011)*$. Но мы еще не закончили, поскольку есть несколько других последовательностей, которые недопустимы для S, но сами по себе являются допустимыми последовательностями и поэтому могут быть соединены с S.

• 0
• 00
• 01
• 001

000, конечно, не допускается, и все, что больше, либо в S, либо само по себе не разрешено.

Таким образом, все регулярные выражения, соответствующие допустимым последовательностям:

^(1|011|0011)*(|0|00|01|001)$

Это ноль или более S последовательностей, за которыми может следовать одна из наших разрешенных не S последовательностей.