I have to give the transition diagram of an NFA accepting all strings that are not empty and start and end with the same symbol, I should also use non-determinism as much as possible (language is {0,1}*). I drew the following diagram: enter image description here

Even thought this is an NFA (as all DFAs are NFAs too), I did not really use non-determinism (I don't have any case where I would go to multiple states at the same time) My question is the following: is it possible to add more non-determinism in this diagram? In general, how can I know that and how to do it if it is possible?

  • $\begingroup$ that not a NFA that recognizes the language that you describe, for instance, it accepting the word $10101$ that does not belong to the language $\endgroup$
    – OriFrid
    Feb 5, 2022 at 10:49
  • $\begingroup$ @DaniTo thank you! what about the other part of my quest? $\endgroup$
    – Sergio
    Feb 5, 2022 at 10:54
  • $\begingroup$ about the second part of your question, that is not a well-defined question, because you don't define what is " more nondeterminism" you always can add state as much that you want and make it more "nondeterministic" $\endgroup$
    – OriFrid
    Feb 5, 2022 at 11:01
  • $\begingroup$ non-determinism is about going to multiple states at the same time which isn't the case here $\endgroup$
    – Sergio
    Feb 5, 2022 at 12:23

1 Answer 1


I'm not aware of measures of nondeterminism for NFAs (though these might exist). The instruction to use as much nondeterminism as possible is informal. It asks you to try to take advantage of nondeterminism in order to construct as simple an automaton as possible. In fact, in your case there doesn't seem to be any reasonable way to employ nondeterminism in order to simplify the automaton.

Here is an informal description of one way to solve your problem:

  • "Guess" (nondeterministically) what is the symbol that the input starts and ends with.
  • Verify that the input conforms to the guess.

In this case, there is no need to guess, since we can just read the first input symbol, so this is an unconvincing application of nondeterminism.


Your Answer

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

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