John,

Preliminaries

Your question is unclear! If it is really "What is the complexity of the class P / NP?" the two automatons presented are not doing anything - I assume that's not what you're after.

For the question to make sense you have to define the statement - complexity to do anything concrete: you have to define / present an algorithm on these automata, it is verified that.

Trying to guess :

Assuming that the two PLCs will be used to recognize whether a 0/1 string is valid, and looking at the two PLCs:

• M1 is a nondeterministic automaton (in state 0 before a "1" I have two possible states to transit.)
• M2 is the deterministic automaton equivalent to machine M1. (probably obtained through a classical non-deterministic automaton conversion algorithm - > deterministic automaton)
• If M1 has n states, the machine M2 can have a maximum of 2 ^ n states (as is the case here) although I usually have a number much smaller than that.

Since M2 is a deterministic machine, the algorithm is obvious: (pass through each input symbol) and the machine recognizer is linear in relation to the length of the input string (O (k))

The time taken by the M2 recognizer will be more time-consuming and will depend on the concrete algorithm used ...