Конечная строка автоматов не заканчивается на ba

Question

Вопрос: Постройте FA, который принимает только те слова, которые не заканчиваются на ba.Я хочу нарисовать DFA для этой проблемы, но я не понимаю, как это сделать, пожалуйста, помогите мне нарисовать это

Answer 1

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

----->(q0)--b-->(q1)--a-->(q2)

Здесь, (q0) принимает, (q1) принимает и (q2) не принимает.(q0) соответствует отсутствию части строки ba, состоянию (q1) - увидению первого символа и (q2) - просмотру всего этого.Следовательно, отсутствующие переходы должны быть:

• q0 к q0 для символа a, так как, если мы еще не начали видеть ba, a не поможет;нам потребовалось ab
• q1 до q1 для символа b, поскольку, если мы видим b, мы всегда по крайней мере видели первый символ в ba
• q2 до q0 по символу a и до q1 по символу bПо указанным выше причинам.

Весь DFA выглядит так:

                /--|--b----\
                b  |       |
                |  V       |
----->(q0)--b-->(q1)--a-->(q2)
      |  ^                 |
      a  |                 |
      \--|-----------------/

Answer 2

RE для языка, который не заканчивается на ba, равен (a+b)*(aa+bb+ab)

здесь язык либо заканчивается на aa или bb, либо ab

чтобы сделать DFA из RE, вы можете использовать эту надежду, что она окажется полезной для вас https://cyberzhg.github.io/toolbox/nfa2dfa

в данном заданном DFA .. он принимает строки длиной 2 или более 2, но не заканчивающиеся на ba