I'm trying to create a FSM that multiplies a bitstream with a constant value (e.g 3).
I don't have a clue how to design such a FSM. Any hints?
$\begingroup$
$\endgroup$
-
2$\begingroup$ What have you tried? What approaches have you considered? Have you tried working through some examples? We discourage posts that simply state a problem out of context, and expect the community to solve it. e do not want to just do your exercise 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. $\endgroup$ – D.W.♦ Mar 5 '16 at 0:38
-
1$\begingroup$ I suggest you read cs.stackexchange.com/q/1331/755, read up on finite-state transducers, and read cs.stackexchange.com/q/7879/755 and cs.stackexchange.com/q/2745/755. $\endgroup$ – D.W.♦ Mar 5 '16 at 0:44
-
$\begingroup$ @D.W. So far I tried just to create a FSM for some possible input strings. But I got lost on the track. And I can't try every possible input string (eve though I hope there is some repetition). I think there needs to be an analytical approach but I couldn't come up with one yet. Yes, this is an homework question. No, I don't want a finished solution. I'm just stuck and need some pointers. $\endgroup$ – woodtluk Mar 5 '16 at 0:55
$\begingroup$
$\endgroup$
Let $x_1 x_2 x_3 \cdots x_n$ denote the input string ($x_i$ is the $i$th bit of the input). Let $y_1 y_2 y_3 \cdots y_n y_{n+1} y_{n+2}$ denote the desired output string ($y_i$ is the $i$th bit of the output).
You want a finite-state transducer that, on input $x_1 \cdots x_n$, outputs $y_1 \cdots y_{n+2}$.
This is equivalent to asking for a deterministic finite-state machine (DFA) that accepts all strings of the form
$$x_1 y_1 x_2 y_2 x_3 y_3 \cdots x_{n-1} y_{n-1} x_n y_n E y_{n+1} E y_{n+2}$$
where $E$ is some special symbol that indicates "there's no more input" (end of the input).
There are lots of resources on how to design a deterministic finite-state automaton (DFA) that accepts a particular language. So, go use those resources to find a DFA that accepts that language. Once you've done that, you will be able to translate it back to a finite-state transducer as required.
-
$\begingroup$ Thanks for the hints. I read some of the stated resources. But still struggling. What if I have different input and output strings? (Basically I have infinite possible inputs) I tried again to do the FSM for some input strings. But I can't manage to do one that works with every possible input. $\endgroup$ – woodtluk Mar 6 '16 at 19:32
-
$\begingroup$ I finally managed to solve the exercise. But it was mostly by try-and-error. But thanks for all the hints! $\endgroup$ – woodtluk Mar 9 '16 at 21:26
