Недетерминированные конечные автоматы

Question

Может ли кто-нибудь объяснить, почему это (автоматы на картинке) NDFA? Это потому, что у него только одно начальное состояние, или потому, что есть несколько стрелок с одним и тем же символом, которые приходят в одно и то же состояние? Я не совсем понимаю, определяет ли одна из этих вещей это как NDFA?

Answer 1

Это недетерминировано, потому что q1 имеет два разных перехода на #.

После (#, машина находится в состояниях q1 а также q3, и примет все @), #@), ##@), так далее.

высказывать q3однако является избыточным. Вы можете просто удалить его, чтобы создать DFA, который принимает тот же язык.