Как нарисовать DFA (или NFA) из простого оператора?

Мне дается простое утверждение: построить DFA над alphabet {0, 1}, который принимает all the strings that end in 101?

Мой вопрос заключается в том, каковы будут шаги по его разработке? Или разработайте NFA, потому что тогда я буду знать четкие шаги по преобразованию NFA в DFA, поэтому я затем преобразую NFA в DFA.

Примечание. Для меня это всего лишь второстепенный курс, поэтому я никогда не изучал ничего похожего на регулярные выражения или какие-либо алгоритмы, которые, вероятно, используются для построения DFA.


regex dfa nfa
person Solace    schedule 24.04.2014    source источник
comment
не используйте для этого регулярные выражения. Просто подумайте, в каких состояниях может находиться конечный автомат.   -  person John Dvorak    schedule 24.04.2014
comment
Вы знаете, как построить простые DFA? Скажем, DFA, который принимает только «1» или «01»?   -  person Matthew    schedule 24.04.2014
comment
@Human Для '1' переход по сигналу 1 начнется с начального состояния и закончится сам по себе, а по сигналу 0 начнется с начального состояния и закончится death (die) state. Таким образом, начальное состояние также будет принимающим состоянием.   -  person Solace    schedule 24.04.2014
comment
@Human Для «01» переходы 0 и 1 будут начинаться в начальном состоянии и заканчиваться, скажем, в самом себе, что делает начальное состояние также принимающим состоянием.   -  person Solace    schedule 24.04.2014
comment
@Human Вот что я думаю. Я не уверен, прав я или нет.   -  person Solace    schedule 24.04.2014
comment
Теперь попробуйте DFA строк, в которых 3-й последний символ равен 1.   -  person Grijesh Chauhan    schedule 25.04.2014

Ответы (1)


arrow_upward
4
arrow_downward

Если вам нужно больше объяснений того, как я это получил, я был бы рад объяснить, но пока я просто нарисовал DFA и объяснил каждое состояние.

Извините за скриншот ... Я не знал, как преобразовать его прямо в изображение.

DFA

  • На входе 0 в состоянии 0 он возвращается к самому себе. На 1 он готовится к завершению, потому что это может быть «101».

  • q1 зацикливается на входе 1, потому что он все еще готовится завершиться на «101». Ввод «0» на q1 означает, что он готовится к вводу «10», поэтому он переходит к q2.

  • Ввод «0» на q2 прерывает весь цикл и возвращается к q0. Ввод «1» приводит к переходу в q3, принимающее состояние.

  • Любой ввод в q3 приводит к возврату к любой точке цикла, которой соответствует ввод.

  • То есть на «1» он возвращается к q1 или состоянию, в котором первая «1» встретилась в «101», готовясь к завершению.

  • На «0» он переходит к q2, потому что для того, чтобы добраться до q3, должна была быть введена «1» из q2, поэтому, несмотря ни на что, последние два входных символа теперь равны «10».

Примеры TikZ DFA.

person Matthew    schedule 24.04.2014
comment
какой у вас инструмент для рисования этой фигуры? - person Grijesh Chauhan; 25.04.2014
comment
@GrjeshChauhan Я использовал пакет TikZ с TeXLive в Latex. :) Я включил ссылку на примеры TikZ DFA в конце своего поста. - person Matthew; 26.04.2014
comment
спасибо, я попробую, я использую dia, но это выглядит более четко. Можем ли мы сделать цветные картинки? - person Grijesh Chauhan; 26.04.2014
comment
@GrjeshChauhan Что ты имеешь в виду? Да, ты можешь. Вы можете делать массу вещей с TikZ/LaTeX в целом. - person Matthew; 26.04.2014