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

Question

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

Answer 1

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

После (# машина находится в состояниях q1 и q3, и будет принимать все @), #@), ##@), et c.

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