Finding a small Moore machine that checks the last four bits I am looking for a Moore finite state machine that returns true if and only if the last 4 bits (the input is of bits) are 0011 or 0101, the FSM can return any value at the first 4 bits (yes, even at the 4th).

The issue is that I was asked for a 7 conditions (vertexes) limit, and despite my efforts could not create one, my questions are the following :


Is there a FSM that solve this at 7 conditions (7 vertexes)? If there is than what is it and if not how can I prove there isn't? 
Is there any type of 'algorithm' to approach this? I can easily well define one if we can use as much conditions as we wish (16 for our case) but what way other than intuition can lead me to reducing to 7 conditions?
Since you have been given an upper limit to number of states, the best way to go about solving this problem is to get a correct solution first independent of number of states and then minimize the automata. Every moore automata has a canonical unique automata of minimum number of states (meaning all minimum state automata are equivalent).

As the solution is following and you cannot minimize the moore automata any further, you can declare that you cannot solve the problem with 7 states:


By the way, minimization of moore automata is similar to minimization of deterministic finite automata. We need to find equivalent states and merge them. Refer DFA Minimization.