Приведите диаграммы состояний DFA, распознающих следующие языки. Во всех частях алфавит {0,1}

Question

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

Приведите диаграммы состояний DFA, распознающих следующие языки.Во всех частях алфавит {0,1}

{w |длина w не более 5}

Answer 1

Вот несколько подсказок.

• «Максимум 5»: это означает, что вы должны провести некоторый подсчет.В конечных автоматах подсчет выполняется контекстом каждого узла.Другими словами, вам потребуется несколько узлов, каждый из которых имеет особое значение, и это значение будет вашим «значением счетчика».
• «Максимум 5»: это означает, что вы должны принимать слова длиной 0, 1, 2, 3, 4 и 5. (Все из которых имеют уникальные значения, подсказка подсказки.)
• Ваш алфавит {0,1}, но нет требований к языку частоты, порядокили что-нибудь связанное с 0 и 1.Это означает, что каждый раз, когда происходит переход для 0, один и тот же переход должен быть доступен для 1, и наоборот.(Или какое-то эквивалентное отношение, которое сводится к этому правилу - но это в скобках, потому что это не то, о чем вам нужно думать.)

Answer 2

Вот ваши ошибки:

• У вас нет отмеченного начального состояния.
• Строки "0", "" (пустая строка), "1" отклоняются, но находятся в пределах предписанного языка. Другими словами, вы принимаете только слова, которые точно длина 5, а не все слова длиной 5 и менее.

Поскольку алфавит {0, 1}, вы должны указать в КАЖДОМ состоянии, что происходит, когда встречается либо 0, либо 1. Если вы встретите входной символ, край которого НЕ указан, по соглашению вы переходите в мертвое состояние, состояние, которое всегда возвращается к себе и никогда не принимается, но остается неиспользованным. Вот почему ваше крайнее правое состояние не является необходимым, но ваше левое состояние является неполным.

Финал, большой совет: у вас может быть несколько состояний "Принять" или "Финал".

Answer 3

Я думаю, что DFA, показанный выше, неверен. Он будет принимать строки длиной до 5, поэтому вы должны сделать все первые шесть состояний конечными. Вы принимаете только «1», но он также должен принимать «0» ...... поэтому добавьте 0 со всеми 1.