Как построить DFA, которая распознает набор битовых строк, который начинается с двух D?

Question

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

вопрос означает, что я должен дать ввод 1101 1101 и, если да, то как показать другое состояние для перехода, если строка битов не начинается с двух D

Answer 1

Предполагая, что D означает шестнадцатеричное представление десятичного числа 13, тогда да, двоичное представление того же числа равно 1101, и набор строк, начинающийся с двух D (то есть шестнадцатеричное представление двоичной строки начинается с двух D), будет набор строк начинается с 11011101. Чтобы принимать такие строки с DFA, вам нужно десять состояний:

• начальное состояние
• одно состояние для каждого символа в вашей строке
• мертвое состояние

Переходы будут идти из исходного состояния в каждое состояние, соответствующее символам вашей строки, по порядку символов в этих позициях. Любой вход, который неуместен, приведет к последнему, мертвому состоянию, которое зацикливается на себе. Единственное принимающее состояние - это состояние, соответствующее последнему символу вашей строки, и оно также зацикливается на себя (поскольку любая строка, образованная добавлением к этой базе, также является строкой на вашем языке)