Различие в конечных автоматах НКА ДКА?

Question

[demsp]

А в чем различие НКА и ДКА ? Например, светофор - это НКА?

Answer 1

[NonameProgrammer]

Значит НКА имеет множество переходов из одного состояния. В то время как ДКА только один. НКА легче спроектировать в уме. Реализовать сложнее. Обычно в компиляторах используют ДКА. А ещё если не ошибаюсь в НКА есть нулевой переход

Answer 2

[Rsa97]

Детерминированный конечный автомат для каждого состояния содержит не более одного перехода для каждого входного символа и не содержит перехода для пустого символа ε.
Светофор вообще к конечным автоматам не относится.

Comments

[demsp]

Сапсибо. А почему не относится (он же из одного состояния переходит в другое )?

[Rsa97]

demser, А какой у него набор входных символов? И какой набор допустимых и недопустимых состояний в которых светофор завершает работу?
Конечный автомат он потому и конечный, что есть конечные (завершающие) состояния.

[NonameProgrammer]

Rsa97, RED, YELLOW, GREEN

[Rsa97]

NonameProgrammer, Это состояния. А входные символы какие. Как я могу подать на вход светофора нужный символ?

[NonameProgrammer]

Rsa97, их 16 значение

[demsp]

Эээ, а светофору (при включении) надо задать начальное значение?

[NonameProgrammer]

demser, при включении обычно проверяются все лампы

[Rsa97]

NonameProgrammer, А какое состояние у светофора конечное допускающее, говорящее, что цепочка входных символов распознаётся данным автоматом?

[demsp]

Тогда такой светофор не подходит под определение FSM. А если у нас светофор, у которого мы должны задавать начальный цвет, то это ДКА?

[Rsa97]

demser, Конечный автомат - это автомат у которого обязательно есть минимум одно допустимое конечное состояние. Оказавшись в нём автомат прекращает работу и сообщает, что цепочка входных символов допустима.

[NonameProgrammer]

Rsa97, я изначально не утверждал, что светофор является автоматом

[demsp]

Да, действительно

Answer 3

[Сергей Соколов]

Основное отличие ДКА и НКА состоит в том, что ДКА в процессе работы может находится только в одном состоянии, а НКА в нескольких состояниях одновременно.

— пост «Регулярные выражения изнутри» на Хабре неплохо объясняет суть конечных автоматов.

Comments

[demsp]

Я как раз прочитал Теория вычислений. Введение в конечные автоматы

Answer 4

[Денис Загаевский]

В общем вам всё сказали, и ещё дополню - для любого НКА можно построить эквивалентный ДКА.