Каким будет DFA для (0+1)*?

Я нарисовал эту схему ниже. Но я хочу быть уверенным в ответе, так как оператор + и * сбивают с толку.

     _  
    | \
--> q_|- 0,1,E

Здесь мой DFA имеет только одно состояние q. Оба 0,1,empty перенаправляются на сам q.


computation-theory
person Nivetha    schedule 05.08.2013    source источник

Ответы (2)


arrow_upward
1
arrow_downward

(0+1) означает, что вы можете выбрать 0 или 1, но не оба. + аналогичен ИЛИ. Звездочка означает, что вы можете сделать этот выбор ноль или более раз.

Следовательно, (0+1)* будет включать любую строку из 0 и 1, включая пустую строку.

person Ishaan    schedule 05.08.2013
comment
Почему только строки из 0 и 1? Рассмотрим 0101. Могу ли я сказать, что для первой буквы я выберу нулевую часть, а для второй я выберу единицу и так далее. Так можно ли принять эту строку? - person Nivetha; 05.08.2013

arrow_upward
0
arrow_downward

С опозданием на 5 лет, но вот что я получил:

Start at A. A is also an end state.

From A: Input 0 goes to B. B is an end state.
        Input 1 goes to C. C is an end state.

From B: Input 0 goes to B.
        Input 1 goes to C.

From C: Input 0 goes to B.
        Input 1 goes to C.

Я почти уверен, что это правильно (готовится к экзамену в банкомате)...

Это может быть трудно визуализировать из этого, но если вы нарисуете диаграмму из моих инструкций, она должна быть более ясной.

Надеюсь, это поможет любому, кто ищет это.

person henry434    schedule 17.04.2019