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?

  • 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

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

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.