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

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?

• Where did you get the definition? For each state and input the transition and output functions give sets of states and output symbols. Probably the choice of state and output should be connected in some way? You cannot assume determinism, for the reason you state. You do not need it. Look for "product construction". Sep 14 '14 at 21:19
• So you are suggesting that $\tau$ outputs some symbol in $\Delta$? But how does this account for the case in which 2 distinct transitions exiting 1 particular state are such that one has the label '$x/y$', while the other has the label '$x/z$', where $y \neq z$? Sep 14 '14 at 21:27
• I may have misread what you wrote. Do you mean that "the transition and output functions give sets of states and [sets of] output symbols [, respectively]"? Sep 14 '14 at 21:42
• Please don't post homework: public.asu.edu/~ccolbou/src/457hw1f14.pdf
– Ryan
Sep 15 '14 at 3:54
• 1. There seem to be some typos in your quesiton. Please proof-read it carefully. You define $M(L)=$ but there is nothing after the equality sign; I assume something got left out. 2. What research have you done? See, e.g., here: en.wikipedia.org/wiki/Finite_state_transducer. Your question should be answered in standard textbooks on automata theory.
– D.W.
Sep 15 '14 at 4:11

## 1 Answer

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.