# Are equalizers of regular functions always regular languages? (My guess is no because PCP, but…)

Edit: I originally defined a regular function as a function computable by a Mealy machine, but Denis pointed out that that was a weaker model than what I was thinking of.

So to be more precise, by a "finite-state transducer" with input alphabet $A$ and output alphabet $B$, I mean a deterministic finite automaton over $(A \cup \{\epsilon\}) \times (B \cup \{\epsilon\})$.

In particular, if both of the following hold for a transducer, then the transducer computes a function:

• Every transition $(q, (x,y), q')$ is uniquely determined by $q$ and $x$;

• If there is a transition $(q, (\epsilon, x), q')$ for any $x$, then there are no other transitions from state $q$.

Feel free to generalize or restrict as desired.

Definitions:

Let $L$ and $M$ be languages. A regular function $f:L\to M$ is a function computable by a finite-state transducer $A$ such that $(l,m)\in L(A)$ if and only if $l \in L$ and $m=f(L)\in M$. Note that it is decidable whether the relation computed by a given FST is a function.

Define the equalizer $Eq(f,g)$ of two regular functions $f,g:A\to B$ as the set of all strings $x\in A$ such that $f(x)=g(x)=y$ for some $y\in B$.

"Theorem": The equalizer of two regular functions is regular.

"Proof": Since $f$ and $g$ are regular functions, they are also regular relations. In particular, we can take their intersection $h=f\cap g$. By definition, we have $(x,y)\in h$ if and only if $(x,y)\in f$ and $(x,y)\in g$; in function notation this becomes $(x,y)\in h$ iff $f(x)=g(x)=y$. By the closure properties of regular relations, it follows that $h$ is a regular relation; and since $f$ and $g$ are functions, $h$ is also a function.

Since $h$ is a regular relation, it is recognized by some finite state transducer $T$. We can take the input projection $\pi_1 T$, giving us a finite automaton which accepts a string $x$ if and only if $(x,y)\in h$ for some $y$. Let $E$ denote the language of the automaton $\pi_1 T$. By the definitions of $h$, $f$, and $g$, it follows that $x\in E$ if and only if $x\in A$ and $f(x)=g(x)=y$ for some $y\in B$. $\square$

But wait. Suppose $A$ is the set of all nonempty strings $\Sigma^+$ over some alphabet $\Sigma$, and suppose $f$ and $g$ are homomorphisms (every homomorphism is a regular function.) Then we can take the equalizer $P=Eq(f,g)$, which is regular by the above "theorem".

Now $P$ will be nonempty iff there is a string $x\in \Sigma^+$ such that $f(x)=g(x)$. In other words, $P$ encodes the Post correspondence problem (PCP) for $f$ and $g$.

But since $P$ is regular, it is recognized by some finite automaton, and emptiness is decidable for finite automata. Since intersection and projection are computable constructions on transducers, we therefore have a method to solve PCP given the transducers for the homomorphisms $f$ and $g$. But this is impossible since PCP is undecidable. So where am I wrong?

• Are you sure that rational/regular relations are closed under intersection? I can't remember whether this is true in general. – Ulrik Rasmussen Mar 2 '16 at 20:45
• I haven't checked it in detail, but Example 2.5 in Berstel's book (Transductions and Context-Free Languages) seems to be a counter-example of this assumption. – Ulrik Rasmussen Mar 2 '16 at 20:54
• Any regular relation can be represented as a regular language though: namely, the transition language of the finite transducer. Deleting "epsilons" is a simple homomorphism, if that's an issue. So it seems they should be closed under intersection. – BenW Mar 2 '16 at 21:09
• I am not familiar with definitions of all these models, hence I cannot pinpoint where exactly it goes wrong, but here’s a very simple example that hopefully will help with that. Consider the alphabet $\Sigma=\{a,b\}$, let $f$ be the homomorphism that deletes $b$, and $g$ the homomorphism that deletes $a$ and renames $b$ to $a$. Then $Eq(f,g)$ is the nonregular language consisting of words with the same number of occurrences of $a$ and $b$. – Emil Jeřábek Mar 2 '16 at 21:10
• Rational relations are not closed under intersection. – Sylvain Mar 2 '16 at 22:45

## 2 Answers

The problem is in your assumption that rational relations are closed under intersection. The following counter-example is taken from Example 2.5 in Berstel's "Transductions and Context-Free Languages":

Let $X, Y \subseteq \{a\}^* \times \{b,c\}^*$ be rational relations defined by \begin{align*} X ={}& \{ (a^n, b^n c^k) \mid n,k \geq 0 \} \\ Y ={}& \{ (a^n, b^k c^n) \mid n,k \geq 0 \} \end{align*}

They are rational since $X = (a,b)^* (1,c)^*$ and $Y=(1,b)^*(a,c)^*$. But the intersection $$Z = X \cap Y = \{ (a^n, b^n c^n) \}$$ is not rational. If there was a transduction $\tau : \{a\}^* \to \mathcal{P}(\{b,c\}^*)$ realizing $Z$, then since transductions preserve regular languages, the language $\tau(a^*) = \{b^n c^n\}$ would be regular, a contradiction.

If you use Mealy machines, it forces your functions to be length-preserving, and therefore you cannot encode PCP with them.

Your regularity theorem holds with length-preserving functions. If you want to allow length-increasing functions (that you need for PCP), you need a more powerful transducer model, for which undecidability quickly kicks in.

• That's right, I forgot Mealy machines had to be deterministic. But the theorem uses constructions defined for nondeterministic transducers as well. So what gives? – BenW Mar 2 '16 at 20:09