Deterministic vs nondeterministic finite automata

Question

I've just asked a question about non-deterministic finite automata but still feel confused. Here is the attached Deterministic Finite Automata: Deterministic diagram

The first node has two transitions and the second one has two as well.

Non-deterministic Finite Automata: Non-deterministic diagram Here the first node has two transitions.

The question is how can I determine if it's a deterministic or nondeterministic finite state? Could please somebody give explanations based on the above attached pictures? Thanks in advance!

Answer 1

The number of transitions a node has isn't what makes it deterministic. What makes a automata nondeterministic is if a state more then one transitions for the same input.

In your second diagram $q_1$ has two transitions labelled with '1'. While in your first diagram every state every transition coming out of a node has a different label.

Answer 2

There are two possible definitions of a deterministic automaton, depending on whether you consider complete automata or allow incomplete ones.

An automaton is complete deterministic if it has exactly one initial state and, for every state $p$ and for every letter $a$, there is exactly one state $q$ such that $p \xrightarrow{a} q$ is a transition.

An automaton is deterministic if it has exactly one initial state and, for every state $p$ and for every letter $a$, there is at most one state $q$ such that $p \xrightarrow{a} q$ is a transition. In the literature, the term deterministic is often used for complete deterministic.

It follows from these definitions that your first automaton is complete deterministic. The second one is not, for two reasons. First, there is an $\epsilon$-transition $q_2 \xrightarrow{\epsilon} q_3$, which is not allowed in a deterministic automaton. Secondly $q_1 \xrightarrow{1} q_1$ and $q_1 \xrightarrow{1} q_2$ are transitions, which contradicts the definition given above.