2
$\begingroup$

Is it possible to constract Moore or Mealy machine to take input tape: 0011 and output: 00001111 (or vice versa). In other words, input and output have different size.

I want to construct FSMs to produce different transformation patters:

  1. copy 2 times: 11 -> 11011, 101 -> 1010101
  2. trim: 011100 -> 111, 000110 -> 11
  3. fill zeros by 1 between 1: 01000100 -> 01111100, 01010 -> 01110

Can you please suggest is it possible to do it with FSM (Moore or Mealy machine) or should I switch to context free languages?

$\endgroup$
3
$\begingroup$

Can you please suggest is it possible to do it with FSM (Moore or Mealy machine)

The machine you are looking for is called a finite-state transducer. They can be defined in either Moore or Mealy variants. For the Mealy variant (which I believe is more common), you have a finite state machine where the edges are labeled with output, and the initial states are also written as initial edges that can have associated output. (That is so that output can be produced on the empty input, if desired).

There are two types of finite-state transducers: one-way transducers and two-way transducers. The difference is that:

  • One-way transducers just read the input from left to right, like a normal state machine.

  • Two-way transducers have, for each edge, a label which says whether they move left, right, or stay still. The input tape also has start and end symbols: for example, the input 001 would be written $\triangleleft 00 1 \triangleright$. The machine has a special "halting" state. It moves back and forth on the input tape, reading symbols and producing output, until it is finished.

Two-way transducers are more expressive than one-way transducers. For some of the tasks you listed, one-way transducers are enough, but all of them can be done with two-way transducers.

  1. copy 2 times: 11 -> 11011, 101 -> 1010101

This can be done with a two-way transducer. It reads the input, producing it as output, then goes back to the start of the tape, produces a zero, and reads the input again, producing it as output again.

  1. trim: 011100 -> 111, 000110 -> 11

A one-way transducer can do this. It only needs one state; then depending on the input symbol, it either produces output or produces no output.

  1. fill zeros by 1 between 1: 01000100 -> 01111100, 01010 -> 01110

A one-way transducer can do this. You should be in a different state depending on whether you want to fill the zeros, or leave them be, and then switch between these states whenever you encounter a 1.

or should I switch to context free languages?

I hope not! Context free languages are much more complex and difficult to work with, and not necessary for the kinds of tasks you list.

$\endgroup$

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.