# How can I know if more non-determinism can be used in an NFA?

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:

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?

• 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 Feb 5, 2022 at 10:49
• @DaniTo thank you! what about the other part of my quest? Feb 5, 2022 at 10:54
• 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" Feb 5, 2022 at 11:01
• non-determinism is about going to multiple states at the same time which isn't the case here Feb 5, 2022 at 12:23

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.