1
$\begingroup$

I've been given following task: Determine the following nondeterministic automaton (omit unreachable states, if they appear during construction)

enter image description here

My solution to this:

enter image description here

Would like to ask for a verification here, especially for the part of this task which is enclosed in parentheses: omit unreachable states, if they appear during construction. I do not fully understand that requirement and therefore I'm not sure if my solution is correct. Did I present some states which should be omitted on the graph/table? I feel like each state is reachable here and maybe task's description itself would have more sense for different example.

Kind regards,

Improve this question
$\endgroup$
2
  • $\begingroup$ Every state is reachable. In addition, every state except $5$ allows to reach a final state. If you are fine with the drawn transitions to be incomplete, you could delete $5$ from the drawing (this is just a convention, formally you still need the extra state in order for the transition function to be a total function). $\endgroup$
    – Steven
    Nov 6, 2021 at 18:26
  • $\begingroup$ got it, thank you :) $\endgroup$
    – crystalsky
    Nov 7, 2021 at 13:49

1 Answer 1

Reset to default
0
$\begingroup$

The generic "theoretical" construction starting from a non-deterministic automaton with state set $Q$ introduces all subsets of $Q$ to be the states of the DFA. This wil introduce many states (subsets) that are nor reachable from the initial states. These states do not contribute to the language, so they can be omitted. From a theoretical point of view this is not relevant, in fact it might be harder to prove correctness if one applies these extra operations.

The "practical" approach (as you have applied here) is to start with the initial state, and to discover (in a breadth-first fashion) what are the states we reach by applying the transition function to sets we got previously.

So, I think you did what was asked. For instance, the state $123$ is not reachable.

Regarding the state $5$, you should realize it represents the empty set (of states) $\varnothing$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.