Approximate Problems for Finite Transducers

It turns out that non-determinism is needed for finite transducers to capture rational functions. A canonical example is the function $f_{\mathrm{𝗅𝖺𝗌𝗍}}:{\{a,b\}}^{\ast }\to {\{a,b\}}^{\ast }$ which moves the last symbol upfront. For example, $f_{\mathrm{𝗅𝖺𝗌𝗍}}(ab\underset{¯}{b})=\underset{¯}{b}ab$ and $f_{\mathrm{𝗅𝖺𝗌𝗍}}(ab\underset{¯}{a})=\underset{¯}{a}ab$. Since the number of symbols that have to be read before reading the last symbol is arbitrarily large, a finite transducer recognising $f_{\mathrm{𝗅𝖺𝗌𝗍}}$ needs non-determinism to guess the last symbol, as illustrated by the following transducer:

So non-determinism, unlike finite automata, brings some extra expressive power when it comes to finite transducers. On the other hand, non-determinism also yields some inefficiency issues when the input is received sequentially as a stream, because the whole input may have to be stored in memory until the first output symbol can be produced. This motivates the class of sequential functions, as the rational functions recognised by input-deterministic finite transducers, and the determinisation problem: given an arbitrary finite transducer, does it recognise a sequential function? In other words, can it be (input-) determinised? This well-studied problem is known to be decidable in PTime [10]. The determinisation problem is a central problem in automata theory. It has been for instance extensively considered for weighted automata [27], and a long-standing open problem is whether this problem is decidable for $(\mathbb{N},max,+)$-automata [25].

The function $f_{\mathrm{𝗅𝖺𝗌𝗍}}$ is not sequential, in other words, the latter transducer is not determinisable. It turns out that $f_{\mathrm{𝗅𝖺𝗌𝗍}}$ is almost sequential, in the sense that it is close to some sequential function, for instance the identity function $\mathrm{𝗂𝖽}$. “Close to” can be defined in different ways, by lifting standard distances between words to functions and relations. Two classical examples are the Hamming distance and the Levenshtein distance, which respectively measure the minimal number of letter substitutions (respectively letter substitutions, insertion and deletion) to rewrite a word into another. A distance $d$ between words is lifted to functions $f_1,f_2$ with the same input domain, by taking the supremum of $d(f_1(u),f_2(u))$ for all words $u$ in their domain. Coming back to our example, $f_{\mathrm{𝗅𝖺𝗌𝗍}}$ and $\mathrm{𝗂𝖽}$ are close for the edit distance, in the sense that $d(f_{\mathrm{𝗅𝖺𝗌𝗍}},\mathrm{𝗂𝖽})$ is finite for $d$ the edit distance, but they are not close for the Hamming distance. This raises a natural and fundamental problem, called approximate determinisation problem (for a distance $d$): given a finite transducer recognising a function $f$, does there exists a sequential function $s$ such that $d(f,s)$ is finite? The approximate determinisation problem has been extensively studied for weighted automata [4, 8, 5] and quantitative automata [6, 7], but, to the best of our knowledge, nothing was known for transducers. However, if both $f$ and $s$ are given (by finite transducers), checking whether they are close (for various and classical edit distances) is known to be decidable, even if $s$ is rational but not sequential [2]. This can be seen as the verification variant of approximate determinisation, while approximate determinisation is rather a synthesis problem, for which only $f$ is given, and which asks to generate $s$ if it exists.

In this paper, our main result is the decidability of approximate determinisation of finite transducers, for a family $ℰ$ of edit distances, which include Hamming and Levenshtein distances. For exact determinisation, determinisable finite transducers are characterised by the so called twinning property (TP) [10, 9, 13], a pattern that requires that the delay between any two outputs on the same input must not increase when taking synchronised cycles of the transducer. As noticed in [2], bounded (Levenshtein) edit distance is closely related to the notion of word conjugacy. In this paper, we consider an approximate version of the twinning property (ATP), with no constraints on the delay, but instead requires that the output words produced on the synchronised loops are conjugate. It turns out that ATP is not sufficient to characterise approximately determinisable transducers, and an extra property is needed, the strongly connected twinning property (STP), which requires that the TP holds within SCCs of the finite transducer. We show that a transducer $𝒯$ is approximately determinisable (for Levenshtein distance) iff both ATP and STP hold and, if they do, we show how to approximately determinise $𝒯$. We also prove that ATP and STP are both decidable.

For Hamming distance, which only allows letter substitutions, determinizable transducers are characterized by both STP and another property called Hamming twinning property (HTP), which roughly requires that outputs on synchronised cycles have same length and do not mismatch. We also show that HTP is decidable, which entails decidability of approximate determinisation for Hamming distance.

We also consider another fundamental problem: the approximate functionality problem. Informally, the approximate functionality problem asks whether a given rational relation $R$ is almost a rational function, in the sense that $d(R,f)$ is finite for some rational function $f$, where $d(R,f)$ is now the supremum, for all $(u,v)\in R$, of $d(v,f(u))$. We prove that the approximate functionality problem is decidable for all the distances in $ℰ$. We prove this problem to be decidable for classical distances, including Hamming and Levenshtein.

Finally, we consider the approximate (sequential) uniformisation problem. In its exact version, this problem asks whether for a given rational relation $R$, there exists a sequential function $f$ with the same domain, and whose graph is included in $R$. This problem is closely related to a synthesis problem, but is unfortunately undecidable [11, 17]. We consider its approximate variant, where instead of requiring that the graph of $f$ is included in $R$, we require that it is close to some function whose graph is included in $R$. However, despite this relaxation, we show that the problem is still undecidable. The proofs omitted are provided in the full version.

Variants of the determinisation problem have been considered in the literature [17]. However, this work considers the exact determinisation of a transducer $𝒯$, by some sequential transducer which is close to $𝒯$, for some notions of structural similarity between transducers. Robustness and continuity notions for finite transducers have been introduced in [22]. While those notions are also based on word distances, the problems considered are different from ours.

Let $A$ or $B$ denote finite alphabets of letters. A word is a sequence of letters. The empty word is denoted by $ϵ$. The length of a word is denoted by $|w|$, in particular $|ϵ|=0$. The $i$th letter of a word $w$, for $i\in \{1,\mathrm{\dots },|w|\}$, is denoted by $w[i]$. The primitive root of $w$ is the shortest word ${\rho }_w$ such that $w\in {\rho }_w^{\ast }$. The set of all finite words over the alphabet $A$ is denoted by $A^{\ast }$. A relation $R\subseteq A^{\ast }\times B^{\ast }$ is sometimes called a transduction, and is said to be functional if it is the graph of a function. We let $\mathrm{𝑑𝑜𝑚}(R)=\{u\in A^{\ast }\mid \exists v\in B^{\ast },(u,v)\in R\}$ be the domain of $R$, and for all $u\in A^{\ast }$, we let $R(u)=\{v\in B^{\ast }\mid (u,v)\in R\}$. Note that $u\in \mathrm{𝑑𝑜𝑚}(R)$ iff $R(u)\ne \mathrm{\varnothing }$.

A (non-deterministic) finite automaton over an alphabet $A$ is denoted as a tuple $𝒜=(Q,I,\mathrm{\Delta },F)$ where $Q$ is the finite set of states, $I\subseteq Q$ the set of initial states, $F\subseteq Q$ the set of final states, and $\mathrm{\Delta }\subseteq Q\times A\times Q$ the transition relation. A run on a word ${\sigma }_1\mathrm{\dots }{\sigma }_n$ is a sequence of states $q_1\mathrm{\dots }{q}_{n+1}$ such that $(q_i,{\sigma }_i,q_{i+1})$ for all $i\in [n]$. It is accepting if and only if $q_1\in I$ and $q_{n+1}\in F$. We denote by $L(𝒜)$ the language accepted by $𝒜$, i.e. the set of words on which there is an accepting run. An automaton is said to be trim if for any state $q$, there exists at least one accepting run visiting $q$. When $𝒜$ is deterministic, we denote the transition function as $\delta :Q\times A\to Q$.

A rational transducer $𝒯$ over an input alphabet $A$ and an output alphabet $B$ is a (non-deterministic) finite automaton over a finite subset of $A^{\ast }\times B^{\ast }$. A transition $(p,(u,v),q)$ of $𝒯$ is often denoted $p{\stackrel{u\mid v}{\to }}_{𝒯}q$. More generally, we write $p{\stackrel{u_1\mathrm{\dots }{u}_n\mid v_1\mathrm{\dots }{v}_n}{\to }}_{𝒯}q$ whenever there exists a run $\rho$ of $𝒯$ from $p$ to $q$ on $(u_1,v_1)\mathrm{\dots }(u_n,v_n)$. The relation recognised by $𝒯$, denoted as $R_{𝒯}\subseteq A^{\ast }\times B^{\ast }$, is defined as $R_{𝒯}=\{(u,v)\mid \exists q_0\in I,q_f\in F,q_0{\stackrel{u\mid v}{\to }}_{𝒯}{q}_f\}$. Relations recognised by rational transducers are called rational relations.

When rational transducers recognise functions, it is often convenient to restrict their transitions to input words of length one exactly, modulo the possibility of producing a word on accepting states. This defines the so-called class of real-time transducers, which is expressively equivalent to rational transducers when restricted to functions. Formally, a real-time transducer (or simply, a transducer in the sequel) $𝒯$ over input alphabet $A$ and output alphabet $B$ is given by a tuple $𝒯=(Q,I,\mathrm{\Delta },F,\lambda )$ where $(Q,I,\mathrm{\Delta },F)$ is a finite automaton over a finite subset of $A\times B^{\ast }$, and $\lambda :F\to B^{\ast }$ is a final output function.

Given a word $u=a_1\mathrm{\cdots }{a}_n\in A^{\ast }$ where $a_i\in A$ for all $i$, a run $\rho$ of $𝒯$ over $u$ is a sequence $q_0\mathrm{\cdots }{q}_n$ such that $q_0\in I$ and $(q_{i-1},a_i,v_i,q_i)\in \mathrm{\Delta }$ for all $i\in [n]$. The input word of the run $\rho$ is $u=a_1\mathrm{\cdots }{a}_n$ and the output word of $\rho$ is $v_1\mathrm{\cdots }{v}_n\cdot \lambda (q_n)$ if $q_n$ is a final state; otherwise, $v_1\mathrm{\cdots }{v}_n$. As for rational transducers, the relation $R_{𝒯}$ recognised by $𝒯$ is defined as the set of pairs $(u,v)$ such that $u$ (resp. $v$) is the input (resp. output) word of some accepting run. We often confuse $𝒯$ with $R_{𝒯}$, and may write $\mathrm{𝑑𝑜𝑚}(𝒯)$ for $\mathrm{𝑑𝑜𝑚}(R_{𝒯})$, or $𝒯(u)$ for $R_{𝒯}(u)$.

The underlying automaton of $𝒯$ is the automaton obtained by projection on inputs, i.e. the automaton $𝒜=(Q,I,{\mathrm{\Delta }}^{\prime },F)$ such that ${\mathrm{\Delta }}^{\prime }=\{(q,a,q^{\prime })\mid \exists (q,a,v,q^{\prime })\in \mathrm{\Delta }\}$. Note that $\mathrm{𝑑𝑜𝑚}(𝒯)=L(𝒜)$. The transducer $𝒯$ is said to be trim if its underlying automaton is trim.

The cartesian product, denoted ${𝒯}_1\times {𝒯}_2$, of two transducers ${𝒯}_i=(Q_i,I_i,{\mathrm{\Delta }}_i,F_i,{\lambda }_i)$, $i\in [2]$, is the transducer $(Q_1\times Q_2,I_1\times I_2,\mathrm{\Delta },F_1\times F_2,\lambda )$ where $((p_1,p_2),a,(v_1,v_2),(q_1,q_2))\in \mathrm{\Delta }$ if $(p_i,a,v_i,q_i)\in {\mathrm{\Delta }}_i$ for $i\in [2]$, and, $\lambda (p_1,p_2)=({\lambda }_1(p_1),{\lambda }_2(p_2))$ for $(p_1,p_2)\in F_1\times F_2$.

Let $𝒯$ be a real-time transducer. When $R_{𝒯}$ is functional, $𝒯$ is said to be functional as well, and the functions recognised by functional transducers are called rational functions. If the underlying automaton of $𝒯$ is unambiguous (i.e., has at most one accepting run on any input), $𝒯$ is referred to as an unambiguous transducer. It is well-known that a function is recognised by real-time transducer iff, it is recognised by a rational transducer [23] iff, it is recognised by an unambiguous transducer [15].

Sequential transducers are those whose underlying automaton is deterministic and they define functions known as sequential functions. In that case, we denote the transition function as $\delta :Q\times A\to Q\times B^{\ast }$. The functions recognised by transducers that are finite disjoint unions of sequential transducers are called multi-sequential functions [14, 24]. The symmetric counterpart of multi-sequential is the class of series-sequential functions.

A transducer $𝒯$ is series-sequential if it is a finite disjoint union of sequential transducers ${𝒟}_1,\mathrm{\dots },{𝒟}_k$ where additionally, for every , there is a single transition from a (not necessarily final) state $q_i$ of ${𝒟}_i$ to the initial state of the next transducer ${𝒟}_{i+1}$. Moreover, the initial state of $𝒯$ is the initial state of ${𝒟}_1$ (the initial states of ${𝒟}_i$ is not considered as initial in $𝒯$, for all $2\le i\le k$). In particular, non-determinism is allowed, for all , only in state $q_i$, from which it is possible to move to ${𝒟}_{i+1}$ or to stay in ${𝒟}_i$. We denote¹¹1This notation should not be confused with the split-sum operator of [3], which is semantically different. such a transducer as ${𝒟}_1\mathrm{\cdots }{𝒟}_k$. A function is series-sequential if it is recognised by a series-sequential transducer.

We recall that a metric on a set $E$ is a mapping $d:E^2\to {ℝ}^{+}\cup \{\mathrm{\infty }\}$ satisfying the separation, symmetry and triangle inequality axioms. Classical metrics between finite words are the edit distances. An edit distance between two words is the minimum number of edit operations required to rewrite a word to another if possible, and $\mathrm{\infty }$ otherwise. Depending on the set of allowed edit operations, we get different edit distances. Table 1 gives widely used edit distances with their edit operations.

Distances between words can be lifted to that between functions from words to words.

It is shown that $d$ is a metric over functions (Proposition 3.2 of [2]). The distance between two functional transducers is defined as the distance between the functions they recognise. A notion closely related to the distance between functions is diameter of a relation. The diameter of a relation $R$ w.r.t. a metric $d$, denoted by ${\mathrm{𝑑𝑖𝑎}}_d(R)$, is defined to be the supremum of the distance of every pair in the relation, i.e., ${\mathrm{𝑑𝑖𝑎}}_d(R)=sup\{d(u,v)\mid (u,v)\in R\}$.

The distance between rational functions and the diameter of rational relation w.r.t. the metrics given in Table 1 are computable [2]. The computability of distance and diameter relies on the notion of conjugacy. Two words $u$ and $v$ are conjugate if there exist words $x,y$ such that $u=xy$ and $v=yx$. In other words, they are cyclic shifts of each other. For example, words $aabb$ and $bbaa$ are conjugate with $x=aa$ and $y=bb$. But $aabb$ and $abab$ are not conjugate. Conjugacy is an equivalence relation over words.

Let us suppose that $𝒮$ satisfies $𝖯\in \{\text{ATP},\text{STP},\text{HTP}\}$, and show that so does $𝒯$. The converse is symmetric. We show this for ATP, and the proofs for STP and HTP, following similar arguments, are provided in the full version. Let $(p_1,p_2,q_1,q_2,u,v,u_1,u_2,v_1,v_2)$ be an instance of the twinning pattern for $𝒯$ with $p_1$ and $q_1$ initial. Since $𝒯$ is trim, there exist words $w,w^{\prime },w_1,w_2$ and two accepting states $p_f,q_f$ such that:

Since $\mathrm{𝑑𝑜𝑚}(𝒯)=\mathrm{𝑑𝑜𝑚}(𝒮)$, for all $i\ge 1$, $u{v}^{i}w,u{v}^i{w}^{\prime }\in \mathrm{𝑑𝑜𝑚}(𝒯)=\mathrm{𝑑𝑜𝑚}(𝒮)$. Iterating the loop of $𝒯$ on $v$ sufficiently many times causes $𝒮$ to also loop on some power of $v$. Formally, there exist $a,b,c\in \mathbb{N}$, states $p_1^{\prime },p_2^{\prime },q_1^{\prime },q_2^{\prime },p_f^{\prime },q_f^{\prime }$ and words $u_1^{\prime },u_2^{\prime },v_1^{\prime },v_2^{\prime },w_1^{\prime },w_2^{\prime }$ such that:

Let $C\in \mathbb{N}$ such that $d(𝒯(x),𝒮(x))\le C$ for all $x\in \mathrm{𝑑𝑜𝑚}(𝒯)$. Then in particular for all $k\ge 0$:

From the above inequalities, using Proposition 2.2, we get that ${\rho }_{v_i}$ and ${\rho }_{v_i^{\prime }}$, the primitive roots of $v_i$ and $v_i^{\prime }$ respectively, are conjugate and $|v_i^b|=|v_i^{\prime }|$ for $i\in [2]$. Since $𝒮$ satisfies the ATP, we also have that $v_1^{\prime }$ and $v_2^{\prime }$ are conjugate, and hence their primitive roots are conjugate and $|v_1^{\prime }|=|v_2^{\prime }|$. By transitivity of the conjugacy relation, we get that ${\rho }_{v_1}$ and ${\rho }_{v_2}$ are conjugate. Further, $|v_1|=|v_2|$ since $|{\rho }_{v_1}|=|{\rho }_{v_2}|$ and $|v_1^b|=|v_1^{\prime }|=|v_2^{\prime }|=|v_2^b|$. Therefore, $v_1$ and $v_2$ are conjugate, and thus the ATP holds for $𝒯$ as well. $◀$

Note that the above lemma does not necessarily hold for TP. For instance, although and the transducer defining the identity function satisfies TP, the transducer defining $f_{\mathrm{𝗅𝖺𝗌𝗍}}$ does not.

We now show that checking each of the variants of the twinning property is decidable.

Let $𝒯$ be a transducer that defines a relation $R$.

Let ${𝒯}^2$ be the cartesian product of $𝒯$ by itself. Verifying whether $𝒯$ satisfies ATP reduces to checking that every loop in ${𝒯}^2$ produces a pair of conjugate output words. For each state $(p,q)\in {𝒯}^2$, we define a rational relation $R_{(p,q)}$ consisting of pairs of output words produced by the loops in ${𝒯}^2$ rooted at $(p,q)$. The transducer defining $R_{(p,q)}$ is obtained from ${𝒯}^2$ by disregarding the inputs and setting both the initial and final state to be $(p,q)$. It is known that we can decide whether every pair of words in a given rational relation is conjugate [1], which entails decidability of ATP.

The twinning property is decidable in polynomial time [10]. To decide STP, we first decompose the transducer into SCCs (in polynomial time). Then, for each SCC and each state $p$, the SCC is seen as a transducer with initial state $p$ on which we check TP.

We prove that it can be decided in PTime whether a transducer does not satisfy HTP. The HTP can be decomposed as a conjunction of two properties : ${\text{HTP}}_{lgth}$ on lengths and ${\text{HTP}}_{mism}$ on mismatches. The (negation of) ${\text{HTP}}_{lgth}$ can be directly expressed in the pattern logic of [18], whose model-checking is in PTime. Then, we reduce the problem of deciding the ${\text{HTP}}_{mism}$ to the emptiness problem of a Parikh automaton of polynomial size, in the size of the transducer $𝒯$. We recall that a Parikh automaton of dimension $d$ is an NFA extended with vectors in ${\mathbb{Z}}^d$ on its transitions. It accepts a word if there exists a run of the NFA that reaches an accepting state, and the sum of the vectors seen along the run belongs to some semi-linear set $W\subseteq {\mathbb{Z}}^d$, given for example as a Presburger formula $\varphi (x_1,\mathrm{\dots },x_d)$. The emptiness problem is known to be decidable in PTime when both $d$ and $\varphi$ are constant [16, 18]. Our reduction follows standard ideas, and falls in this particular case. Let us give a bit more details.

A twinning pattern $t$ can be encoded as a word $u_t$ over ${\mathrm{\Delta }}^2\cup \{\mathrm{\#}\}$, where $\mathrm{\Delta }$ is the transition relation of $𝒯$. In this construction, a run of $𝒯$ is seen as a sequence of transitions. So, a twinning pattern consists of four runs, $r_1,r_1^{\prime }$ and $r_2,r_2^{\prime }$ where for all $i=1,2$, $r_i$ is the run such that $p_i\stackrel{u|u_i}{\to }{q}_i$ and $r_i^{\prime }$ is the run such that $q_i\stackrel{v|v_i}{\to }{q}_i$. The four runs are encoded as a word $u_t=(r_1\otimes r_2)\mathrm{\#}(r_1^{\prime }\otimes r_2^{\prime })$ where $r_1\otimes r_2$ is the convolution of $r_1$ and $r_2$, i.e. the overlapping of $r_1$ and $r_2$ (and similarly for $r_1^{\prime }\otimes r_2^{\prime }$). It should be clear that the set of words $u_t$ for all twinning pattern $t$ such that $p_1$ and $p_2$ are initial states is a regular language, recognizable by an NFA of polysize in the size of $𝒯$.

In order to check the condition that there is a mismatch between $u_1{v}_1$ and $u_2{v}_2$ on a position common to $v_1$ and $v_2$, the NFA is extended with two counters $c_1$ and $c_2$, and the linear acceptance condition $c_1=c_2=0$ (making it a Parikh automaton). Those two counters are used to guess the mismatching position. Initially, using an $ϵ$-loop, those two counters are incremented in parallel. At the end of this first phase, they therefore hold the same value, say $i\in \mathbb{N}$. Then, the Parikh automaton is built in such a way that it checks that and , and $(u_1{v}_1)[i]\ne (u_2{v}_2)[i]$. To do so, while reading any transition of $r_j$ producing some word ${\alpha }_j$, $j=1,2$, $c_j$ is decremented by $|{\alpha }_j|$. The same is done when reading transitions of $r_j^{\prime }$, but the automaton can non-deterministically guess that the counter $c_j$ is equal to $0$, and store (in its state) the corresponding letter in ${\alpha }_j$. From then on, it never decrements the counter $c_j$ again. When the whole input $(r_1\otimes r_2)\mathrm{\#}(r_1^{\prime }\otimes r_2^{\prime })$ has been read, the automaton has two letters stored in its state. It accepts the input, if those two letters are different, and if $c_1=c_2=0$. $◀$

We show with Proposition 4.4 that ATP and STP are necessary conditions for approximate determinisation with respect to Levenshtein family, a consequence of Lemma 3.6. The main challenge lies in proving that these properties are sufficient. To prove it, we first show that ATP alone suffices for certain subclasses of functional transducers: it enables the approximate determinisation of multi-sequential (Lemma 4.6) and unambiguous series-sequential (Lemma 4.7) functions. However, for rational functions in general, ATP does not suffice. For example, the transducer above for $f_{\mathrm{𝗅𝖺𝗌𝗍}}^{\ast }$ satisfies ATP but is not approximately determinisable. To extend this result to all rational functions, we incorporate STP. Given a functional transducer $𝒯$ satisfying STP, we transform each strongly connected component of $𝒯$ into a sequential transducer, effectively decomposing $𝒯$ into a finite union of concatenations of sequential transducers. We then leverage our results for series-sequential and multi-sequential functions to approximate this structure with a sequential function (Lemma 4.8).

Figure 1 illustrates the main construction technique used in these proofs: Starting with a transducer $𝒯$ that we aim to approximate, we construct a sequential transducer ${𝒟}_1$ as follows. We apply the powerset construction to $𝒯$, introducing a distinguished state (marked by a $\bullet$ in the figure) in each subset. The output is determined by the distinguished state’s production. If the distinguished state reaches a point where it has no continuation, we simply transition to another distinguished state. We show that ATP, combined with a carefully chosen priority scheme for selecting distinguished states, ensures bounded Levenshtein distance.

The proof strategy is similar to the Levenshtein setting: We first show that HTP and STP are necessary conditions for approximate determinisation with respect to Hamming distance, we show that HTP alone suffices for the approximate determinisation of multi-sequential and series-sequential functions, and then we conclude by using STP to transform functional transducers into a finite unions of concatenations of sequential transducers.

While the core ideas remain similar to those used for the Levenshtein family, the constructions required for the Hamming distance, illustrated in Figure 1, are more intricate. Approximating the transducer $𝒯$ with respect to the Levenshtein distance (as shown by ${𝒟}_1$ in the figure) allows us, at each step, to select a run, produce its output, and disregard other possible runs. However, for the Hamming distance, it is crucial to carefully track the length difference between the produced output and the potential outputs of alternative runs. For instance, compare the outputs of $𝒯$, ${𝒟}_1$, and ${𝒟}_2$ after reading $babcccc$ :

We observe that after reading the input $bab$, ${𝒟}_1$ realizes that its distinguished state is incorrect and jumps to another state. However, this shift causes a misalignment with $𝒯$, and reading additional $c$’s results in arbitrarily many mismatches.²²2The Levenshtein distance remains bounded, as inserting a letter at the start resynchronizes both outputs. In contrast, ${𝒟}_2$ keeps in memory the delay relative to other runs. Although it may still introduce mismatches along the way, it ensures that when the distinguished run terminates, it adjusts the output while transitioning to another run, preventing long-term misalignment with $𝒯$.