4
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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". $\endgroup$ – Hendrik Jan Sep 14 '14 at 21:19
  • $\begingroup$ 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$? $\endgroup$ – David Smith Sep 14 '14 at 21:27
  • $\begingroup$ 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]"? $\endgroup$ – David Smith Sep 14 '14 at 21:42
  • 3
    $\begingroup$ Please don't post homework: public.asu.edu/~ccolbou/src/457hw1f14.pdf $\endgroup$ – Ryan Sep 15 '14 at 3:54
  • 2
    $\begingroup$ 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. $\endgroup$ – D.W. Sep 15 '14 at 4:11
1
$\begingroup$

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.

$\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.