0
$\begingroup$

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 :

  1. 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?
  2. 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?
$\endgroup$
  • $\begingroup$ I think you should modify the question title, to say it is about minimization of moore automata. $\endgroup$ – Shreesh Feb 7 '16 at 16:15
  • $\begingroup$ What have you tried? Where did you get stuck? We do not want to just do your (home-)work for you; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for a relevant discussion. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? You may also want to check out our reference questions. $\endgroup$ – Raphael Feb 9 '16 at 8:26
1
$\begingroup$

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: enter image description here

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.

$\endgroup$
  • $\begingroup$ hi, first thank you for the answer, is there a deterministic algorithm for minimization of finite automata? in addition, there is not outgoing arrow for the bit "1" on the most right button vertex of the automata you present here. $\endgroup$ – Matan L Feb 7 '16 at 16:20
  • $\begingroup$ I will correct it. and yes there is an algorithm for minimization of deterministic finite automata. I will provide the link. $\endgroup$ – Shreesh Feb 7 '16 at 16:26
  • $\begingroup$ thank you, seems like this is much more interesting than i thought this is :) $\endgroup$ – Matan L Feb 7 '16 at 16:32
  • 1
    $\begingroup$ This is a Mealy automata, not a Moore automata. Moore automata output based on state, not on transitions. $\endgroup$ – DylanSp Feb 8 '16 at 13:55
  • $\begingroup$ Yes you are correct, but above can be easily modify to be a Moore automata. I will redraw it. $\endgroup$ – Shreesh Feb 8 '16 at 13:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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