Блог

Главная - Вопросы по программированию - Регулярное выражение [ 1 ( 0 1* 0)* 1 ]* DFA

Регулярное выражение [ 1 ( 0 1* 0)* 1 ]* DFA

#regex #automata #dfa #automata-theory

#регулярное выражение #автоматы #dfa #теория автоматов

Вопрос:

Каковы условия для того, чтобы цепочка была принята этим регулярным выражением?

Ответ №1:

* в конце может означать, что начальное состояние принимает и что автомат возвращается в это состояние всякий раз, когда он что-либо принимает. Вызовите начальное состояние q1.

Чтобы принять 1 (01 * 0)1, мы должны сначала использовать 1 и перейти в новое состояние, скажем, q2. Оттуда мы можем самостоятельно выполнить цикл для подвыражения 01 * 0, перейдя в новое состояние, q3, на 0, затем выполнив цикл на 1 в q3, затем вернувшись к q2 на 0.

Из q2 мы можем вернуться к q0 на 1. Наш DFA выглядит следующим образом:

      /--1--  /--0--
     |       |     |
     V      | V     |
--->(q1)-1->(q2)-0->(q3)-
     |               ^    
     0               |    /
     |               -1-/
     V
    (q4)-
     ^    
     |    /
     ,1/

Что-то вроде этого должно это сделать.

Ответ №2:

Если вы не знаете, с чего начать, вам следует записать несколько первых элементов, сгенерированных регулярным выражением. В этом случае: 

 SET = {eps, 11, 1001, 10101, ...}

а затем попытайтесь что-нибудь придумать. Впрочем, вы получили ответ, так что я не собираюсь это повторять.

Ответ №3:

Может у вас появится какая-нибудь идея

 [[0-9s] .*]*

Демонстрация:https://rubular.com/r/n3bVXJd3SFffr0