<p>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":</p>

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

<p>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.</p>

CC BY-SA 3.0
2016-03-03T09:38:36.360Z
2016-03-03T09:38:36.360Z
Ulrik Rasmussen
<p>If you use Mealy machines, it forces your functions to be length-preserving, and therefore you cannot encode PCP with them.</p>

<p>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.</p>

CC BY-SA 3.0
2016-03-02T20:09:06.303Z
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
CC BY-SA 3.0
2016-03-02T19:28:57.513Z
2016-03-02T19:28:57.513Z
Denis
<p><strong>Edit:</strong> 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.</p>

<p>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\})$. </p>

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

<ul>
<li><p>Every transition $(q, (x,y), q')$ is uniquely determined by $q$ and $x$;</p></li>
<li><p>If there is a transition $(q, (\epsilon, x), q')$ for any $x$, then there are no other transitions from state $q$.</p></li>
</ul>

<p>Feel free to generalize or restrict as desired.</p>

<hr>

<p><strong>Definitions</strong>:</p>

<p>Let $L$ and $M$ be languages. A <em>regular function</em> $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. </p>

<p>Define the <em>equalizer</em> $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$.</p>

<p><strong>"Theorem":</strong> The equalizer of two regular functions is regular.</p>

<p><strong>"Proof":</strong> 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.</p>

<p>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$</p>

<p><strong>But wait.</strong> 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".</p>

<p>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$. </p>

<p>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. <strong>So where am I wrong?</strong></p>

CC BY-SA 3.0
2016-03-02T20:45:45.347Z
Are you sure that rational/regular relations are closed under intersection? I can't remember whether this is true in general.
Ulrik Rasmussen
CC BY-SA 3.0
2016-03-02T20:54:53.997Z
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
CC BY-SA 3.0
2016-03-02T21:09:55.183Z
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
CC BY-SA 3.0
2016-03-02T21:10:17.560Z
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
CC BY-SA 3.0
2016-03-02T21:34:16.703Z
BenW: I think you are mistaken. Regular languages are rational subsets of *free* monoids, but rational relations are rational subsets of the product monoid of two free monoids, which is not free.
Ulrik Rasmussen
CC BY-SA 3.0
2016-03-02T22:45:22.957Z
Rational relations are not closed under intersection.
Sylvain
<fl.formal-languages><automata-theory><proofs><undecidability><post-correspondence>
Are equalizers of regular functions always regular languages? (My guess is no because PCP, but...)
BenW
# Are equalizers of regular functions always regular languages? (My guess is no because PCP, but...)

(Asked by: username_0 on 2016-03-02)

**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?**

**Tags:** fl.formal-languages, automata-theory, proofs, undecidability, post-correspondence
> **Comments:**
> **username_1**: Are you sure that rational/regular relations are closed under intersection? I can't remember whether this is true in general.  
> **username_1**: 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.  
> **username_0**: 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.  
> **username_2**: 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$.  
> **username_1**: BenW: I think you are mistaken. Regular languages are rational subsets of *free* monoids, but rational relations are rational subsets of the product monoid of two free monoids, which is not free.  
> **username_3**: Rational relations are not closed under intersection.  

---

## 2 answers

### Answer by username_1 on 2016-03-03. Score: 4 | Accepted answer

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.


---

### Answer by username_4 on 2016-03-02. Score: 4

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.

> **Comments:**
> **username_0**: 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?  

---

