Given a non-deterministic Mealy machine $M$, if $L$ is regular, is $M(L)$ regular?

Question

Consider a nondeterministic Mealy machine, $M$, defined as follows: $M = (Q, \Sigma, \Delta, \delta, \tau, q_0)$ where

1. $Q$ is a finite set of states
2. $\Sigma$ is an input alphabet
3. $\Delta$ is an output alphabet
4. $\delta : Q \times \Sigma_{\varepsilon} \to \mathcal{P}(Q)$ is the transition function
5. $\tau : Q \times \Sigma_{\varepsilon} \to \mathcal{P}(\Delta)$ is the output function
6. $q_0 \in Q$ is the start state

Let $M(x)$ for $x \in \Sigma^*$ denote the set of all strings that $M$ could output on input $x$. Note that $M$ could fail to process the entirety of its input, and thus a string is output only if $M$ processes all of its input. Also, we define, for $L \subset \Sigma^*$, $M(L) = \bigcup\limits_{w \in L} M(w)$. Given this, if $L$ is regular, does it follow that $M(L)$ is regular?

I've attempted to solve this by first showing that for every non-deterministic Mealy machine, there exists an equivalent deterministic Mealy machine. By "equivalent" I mean that the input-output behavior of the two is identical. The problem, however, is that the output function for a deterministic Mealy machine can only output a single character at a time. How, then, could I get the simulating deterministic Mealy machine to output a set of strings?

Answer 1

There is no reason to convert the Mealy machine to a deterministic one – indeed, this is not always possible. Suppose that the input alphabet is unary but the output is binary. A deterministic machine has one output of each length, but a non-deterministic machine can have many.

Instead, the idea is to construct an NFA which keeps track of both the Mealy machine $M$ and a machine $T$ accepting $L$. Denote by $w$ the (unknown) word in $L$ on which we run $M$. At each point in time we guess the next symbol in $w$ and transition in $T$, guess a corresponding transition in $M$, and "accept" the symbol output by the $M$-transition (if any). The accepting states of the NFA are those in which $T$ is at an accepting state.

I'll let you go over the details.