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

Question

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

Answer 1

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

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

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

Answer 2

Можете ли вы получить представление

\[[0-9\s]+.*\]\*

Демо: https://rubular.com/r/n3bVXJd3SFffr0

Answer 3

Знак * в конце может означать, что начальное состояние принимает и что автомат возвращается в это состояние всякий раз, когда он что-либо принимает. Назовите начальное состояние 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)-\
     ^    \
     |    /
     \0,1/

Что-то подобное должно делать это.