Complement of Mealy machine

Question

How could one reasonably define and construct the complement of a deterministic Mealy machine?

My intuition is that the complement should give exactly the opposite of output strings after a specific input string. I think this means the complement is non-deterministic. So let's define a (non-deterministic) Mealy machine: $\mathcal{M} = \langle S,I,\Sigma,\Omega,\delta,\lambda\rangle$, where

• $S$ is a finite nonempty set of states,
• $I \subseteq S$ is the nonempty set of initial states,
• $\Sigma$ is a finite input alphabet,
• $\Omega$ is a finite output alphabet,
• $\delta: S \times \Sigma \to 2^S$ is the transition function, and
• $\lambda: S \times \Sigma \to 2^\Omega$ is the output function.

A Mealy machine is deterministic iff $\vert I\vert = 1 \land \forall s \in S, \forall i \in \Sigma: \vert\delta(s, i)\vert \leq 1 \land \vert\lambda(s, i)\vert \leq 1$.

I believe defining and constructing the complement is easier if we assume the transition function, and output function are total. That is fine for me.

So, given a Mealy machine $\mathcal{M}$ how would one define, and construct (using an algorithm) the complement $\overline{\mathcal{M}}$?

If the algorithm follows trivially from the definition of $\overline{\mathcal{M}}$ that is fine too.

My first idea is that one could, for every transition, add new transitions (from, and to the same state) that give exactly the complement of outputs. However, I am afraid I am missing important corner cases.

Answer 1

You are right: it is easy to miss corner cases, so whatever you choose to define, you will need to prove that you defined the right thing.

To do so, you need to first define what you actually want, i.e., the language of $\overline{M}$.

From what I can tell, you want $$\mathcal{L}(\overline M) = \{ (w^I_0 ,w^O_0) (w^I_1 ,w^O_1) \ldots \in (\Sigma \times \Omega)^\omega \mid (w^I_0,w^O_0) (w^I_1 ,w^O_1) \ldots \not\in \mathcal{L}(M)\}$$

If you just just invert the set of possible outputs along an edge, then get an automaton $\overline M$ for which you can then try to prove that it has the right language, i.e., that (1) every word accepted by the automaton is in the language that we defined for it, and (2) vice versa.

Because this seems to be connected to your research, I will not give you the answer whether such a proof works (as I don't want you to force to give non-citation credit to the work of others, which you would need to do if someone else gives you a solution), but rather let you try this out on your own.

Should this approach not work, here is an idea that allows you to cover all corner cases:

• Translate the Mealy automaton to a DFA (deterministic automaton over finite words) that accepts all prefix traces of the Mealy automaton's language
• Complement the DFA
• Conjunct the DFA with with a DFA accepting all words from $(\Sigma \times \Omega)^*$.
• The resulting automaton accepts the words that you want your Mealy automaton to have. So define a suitable translation to a non-deterministic Mealy automaton.

The idea here is the complementation part is done by a well-known and known-to-work algorithm, so you avoid parts of your problem. The last step is still non-trivial, but probably easier than before.