Вместо этого используйте машины Тьюринга…
Название немного вводит в заблуждение. Это должно быть: «Не используйте детерминированные конечные автоматы (DFA). Вместо этого используйте машины Тьюринга».
Использование DFA там, где требуется машина Тьюринга, обойдется вам с точки зрения сложности кода.
И DFA, и машина Тьюринга являются конечными автоматами. Оба имеют состояния и переходы, разница в следующем:
- DFA имеет только состояния и переходы. Его память ограничена только знанием того, в каком состоянии он находится. Учитывая новый ввод или событие, исходя из его текущего состояния, он может перейти в новое состояние (или остаться в текущем состоянии). Он не может вернуться назад и прочитать более ранние входные данные или события. Он просто продолжает потреблять входные данные, пока их не останется.
- У машины Тьюринга есть память; он может вернуться и прочитать любые предыдущие входные данные (или приостановить чтение), а также изменить входные данные и свою память. Он использует как входные данные, так и память, чтобы решить, каким будет его следующее состояние (может быть одним и тем же состоянием).
Good Read: Понимание конечных автоматов.
Так в чем же дело?
Конечные автоматы идеально подходят для задач, которые включают последовательность операций и логику, определяющую, какая операция будет выполняться после текущей, например, на основе данных, которыми вы управляете, входных данных от пользователя, ответов от ожидающих задач, тайм-аутов и других данных. Мероприятия.
DFA отлично подходят для задач, которым требуется мало памяти. Турникет — классический пример. Он закрыт для входа, пока вы не вставите монету. Затем он открывается, чтобы впустить одного человека, после чего снова закрывается. Промыть и повторить.
Турникету не нужна память, кроме текущего состояния. Ему не нужно возвращаться и читать более ранние входные данные. Итак, да, ДФА.
С другой стороны, более сложная система, такая как панель электронного сейфа, потребует памяти для отслеживания кодов и возможности вернуться назад и прочитать ввод (или отложить ввод до более подходящего состояния), и, следовательно, лучше подходит для машины Тьюринга. .
Если мы используем DFA, нам нужно будет предоставить память и много связующего кода. Реализация разбивается повсюду.
Кошмар.
Другой способ взглянуть на эти два:
- Токарные станки могут делать что угодно с DFA, а не наоборот.
- Любая компьютерная программа является машиной Тьюринга.
Поэтому, если вы думаете о своей следующей реализации и видите дискретные состояния и думаете: «Конечный автомат!», сделайте паузу и подумайте, нужен ли вам DFA или машина Тьюринга.
В следующей статье мы рассмотрим машины Тьюринга: на что обратить внимание, построить или купить (скачать) и т. д.