Re: Question on language regularity

Eric Bodden <eric.bodden@xxxxxxxxxxxxxx> wrote:
On Sep 1, 2:17 pm, d...@xxxxxxxxxxxxxxxxxxxxxxxx (David Wagner) wrote:
Can you come up with a regular transducer (a Mealy/Moore machine)
that produces a_2 a_1 a_4 a_3 ... a_(2n) a_(2n-1) as its output when
given a1 a2 a3 ... a_(2n) as its input?

Hmm, I don't think so. I am not sure how to define the output function
in that case.

Write a machine that maps a1 a2 a3 ... a2n to the word (a1,a2) (a3,a4)
.... (a2n-1, a2n). Then write a machine that maps that word to a2 a1 a4
a3 ... a2n a2n-1.

Tor Myklebust
.