Question

Wikipedia states that a Deterministic State Automation "produces a unique computation (or run) of the automaton for each input string".

I always understood this as there being only 1 possible path to compute any unique string. In which case, the following is a DSM.

But now i'm overthinking this and interpreting the description as each input string having a single possible path, and that path is unique from all other input strings. In which case, the following isn't a DSM as '11' and '12' follow the same paths.

So my question is, is the following a DSM or NDSM?

enter image description here

Was it helpful?

Solution

Its still deterministic, there is only one possible path for each input from each state. 1, and 2 can only go back to itself, for it to be non deterministic, the input should have multiple possible paths. Such as if input 1 had two possible states branching from one specific state.

In short, if there are not branching paths for a specific input, and no ε-edges in the graph, it should be deterministic. i.e. no branching paths, we can determine for sure where it goes. The one you drew above we can always determine the path for a specific input.

OTHER TIPS

It is surely a Deterministic Finite Automata as it has unique path for every move defined for any of the state.

If we input 1 to this automata, there is only one unique move defined for 1 from initial to the final state. After reaching final state, we don't care if the input is 1 or 2. Had there been multiple moves defined for any state, it would be Non-deterministic Finite Automata.

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top