Parsing and transduction

Suppose we have an FST and an input-output pair. We will distinguish three problems. We can ask whether the pair belongs to the relation, which we will call recognition. We can instead ask which successful paths support the pair, which we will call parsing. Or we can fix only the input and ask which outputs the machine can produce, which we will call transduction. This last problem is ordinary FST application (Kaplan and Kay 1994; Mohri 1997).

Three problems

Let $T = \langle Q, \Sigma, \Gamma, \delta, q_0, F\rangle$ be an FST.

The pair-recognition problem takes $x \in \Sigma^*$ and $y \in \Gamma^*$ as input and returns whether $\langle x,y\rangle \in \mathbb{R}(T)$.

The pair-parsing problem takes the same inputs and returns the successful paths whose input label is $x$ and whose output label is $y$. Multiple paths may support the same pair.

The transduction problem fixes only $x$ and returns

\[ T(x) = \{y \in \Gamma^* \mid \langle x,y\rangle \in \mathbb{R}(T)\}. \]

Pair recognition is thus a yes-or-no question, while parsing and transduction return sets of objects.

Configurations

How can one search procedure keep the two tapes synchronized? We can adapt the FSA parsing algorithm by recording two string positions. A configuration for pair recognition is a triple $\langle q,i,j\rangle$, where $q$ is the current state, $i$ is the number of input symbols consumed, and $j$ is the number of output symbols consumed.

Write $x=x_1\ldots x_n$ and $y=y_1\ldots y_m$, using one-based string indices, while $i$ and $j$ record how many symbols have already been consumed. Suppose the machine contains a transition $q\xrightarrow{a:b}q'$. Its successor is determined by four cases:

If $a\neq\epsilon$ and $b\neq\epsilon$, require $i<n$, $j<m$, $a=x_{i+1}$, and $b=y_{j+1}$; then move to $\langle q',i+1,j+1\rangle$.
If $a\neq\epsilon$ and $b=\epsilon$, require $i<n$ and $a=x_{i+1}$; then move to $\langle q',i+1,j\rangle$.
If $a=\epsilon$ and $b\neq\epsilon$, require $j<m$ and $b=y_{j+1}$; then move to $\langle q',i,j+1\rangle$.
If $a=b=\epsilon$, move to $\langle q',i,j\rangle$ without a symbol check.

A transition is unavailable when its required bound or symbol check fails. Thus, no search edge reads beyond either string or consumes a mismatching symbol.

The initial configuration is $\langle q_0,0,0\rangle$. A configuration is accepting just in case it has the form $\langle q,|x|,|y|\rangle$ with $q \in F$. We can search the finite graph of configurations with the same depth-first or breadth-first procedures we used for FSAs. Backpointers recover the paths.

Why is this search correct? A configuration $\langle q,i,j\rangle$ should be reachable if and only if $T$ has a path from $q_0$ to $q$ whose input label is $x_1\ldots x_i$ and whose output label is $y_1\ldots y_j$. This is the configuration invariant. The initial configuration satisfies it using the length-zero path. Each search edge follows one FST transition, checks any non-epsilon label against the next symbol on the corresponding tape, and advances exactly the indices whose symbols were consumed. So every configuration added by the search has a witnessing path. Conversely, the next transition on any path with the required labels passes those same checks, so the search includes it. Induction on path length gives both directions.

At an accepting configuration, the invariant says that the corresponding path has consumed all of $x$ and all of $y$ and ends in a final state. This is exactly the definition of $\langle x,y\rangle\in\mathbb{R}(T)$. Thus, reaching an accepting configuration is sound and complete for pair recognition.

There are at most $|Q|(|x|+1)(|y|+1)$ configurations. Even when the transducer has epsilon cycles, memoizing visited triples thus makes the recognition search finite. Backpointers can compactly record multiple successful paths; as with FSA parsing, explicitly enumerating paths may still be infinite when a cycle can be traversed arbitrarily many times.

For transduction, we do not know $y$ in advance, but every transition must still match the fixed input $x$. A configuration instead records the output produced so far:

\[\langle q,i,u\rangle,\]

where $u \in \Gamma^*$. From $\langle q,i,u\rangle$, a transition $q\xrightarrow{a:b}q'$ is available only if either (i) $a=\epsilon$, or (ii) $i<|x|$ and $a=x_{i+1}$. In the first case set $i'=i$; in the second set $i'=i+1$. Set $u'=u$ when $b=\epsilon$ and $u'=ub$ otherwise, and move to $\langle q',i',u'\rangle$. Every accepting configuration with $i=|x|$ contributes its $u$ to $T(x)$. These checks ensure that each reported output is paired with the requested input rather than with some other path label.

Epsilon cycles

The transduction search need not be finite. If a reachable cycle consumes no input but produces output, a fixed input may have infinitely many outputs. Even an $\epsilon:\epsilon$ cycle can cause a naive path enumerator to revisit the same configuration forever.

So a terminating implementation must handle two cases. First, both searches maintain a visited set of complete configurations. For pair recognition, the key is $\langle q,i,j\rangle$; for transduction, it is $\langle q,i,u\rangle$. Memoization makes an $\epsilon:\epsilon$ self-loop harmless because it reproduces a configuration that has already been processed.

Second, memoization alone does not terminate every transduction. A cycle labeled $\epsilon:a$, for instance, reaches the distinct configurations $\langle q,i,a\rangle$, $\langle q,i,aa\rangle$, and so on. The bounded homework API thus imposes the input-epsilon acyclicity condition (IEAC): no cycle that is reachable from the initial state and can reach a final state may consist entirely of transitions whose input label is $\epsilon$. This condition excludes both productive $\epsilon:a$ cycles and nonproductive $\epsilon:\epsilon$ cycles; the visited set remains necessary as a defensive check for repeated configurations. An unrestricted implementation must instead bound output length or return a symbolic representation of the infinite output language.

Two one-state machines expose the distinction. An $\epsilon:\epsilon$ self-loop makes a naive path search diverge but produces only the repeated configuration $\langle q,0,\epsilon\rangle$, which memoization suppresses. An $\epsilon:a$ self-loop produces $a^r$ for every $r\geq0$, so no finite explicit enumeration can return all outputs; IEAC rejects that transducer for the bounded API.

Question

Can a functional FST have more than one successful path for the same input?

Answer

Yes. Functionality constrains outputs, not paths. Several paths may consume the same input as long as they all produce the same output.

The unweighted algorithms treat every successful path alike. In weighted automata, the forward algorithm sums over those paths, while the Viterbi algorithm finds the least-cost or highest-probability one (Rabiner 1989).

References

Kaplan, Ronald M., and Martin Kay. 1994. “Regular Models of Phonological Rule Systems.” Computational Linguistics 20 (3): 331–78. https://aclanthology.org/J94-3001/.

Mohri, Mehryar. 1997. “Finite-State Transducers in Language and Speech Processing.” Computational Linguistics 23 (2): 269–311. https://aclanthology.org/J97-2003/.

Rabiner, Lawrence R. 1989. “A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition.” Proceedings of the IEEE 77 (2): 257–86. https://doi.org/10.1109/5.18626.

--- title: Parsing and transduction bibliography: ../../references.bib --- Suppose we have an FST and an input-output pair. We will distinguish three problems. We can ask whether the pair belongs to the relation, which we will call **recognition**. We can instead ask which successful paths support the pair, which we will call **parsing**. Or we can fix only the input and ask which outputs the machine can produce, which we will call **transduction**. This last problem is ordinary FST application [@kaplan1994regular; @mohri_fst_1997]. ## Three problems Let $T = \langle Q, \Sigma, \Gamma, \delta, q_0, F\rangle$ be an FST. The **pair-recognition problem** takes $x \in \Sigma^*$ and $y \in \Gamma^*$ as input and returns whether $\langle x,y\rangle \in \mathbb{R}(T)$. The **pair-parsing problem** takes the same inputs and returns the successful paths whose input label is $x$ and whose output label is $y$. Multiple paths may support the same pair. The **transduction problem** fixes only $x$ and returns $$ T(x) = \{y \in \Gamma^* \mid \langle x,y\rangle \in \mathbb{R}(T)\}. $$ Pair recognition is thus a yes-or-no question, while parsing and transduction return sets of objects. ## Configurations How can one search procedure keep the two tapes synchronized? We can adapt the FSA parsing algorithm by recording two string positions. A configuration for pair recognition is a triple $\langle q,i,j\rangle$, where $q$ is the current state, $i$ is the number of input symbols consumed, and $j$ is the number of output symbols consumed. Write $x=x_1\ldots x_n$ and $y=y_1\ldots y_m$, using one-based string indices, while $i$ and $j$ record how many symbols have already been consumed. Suppose the machine contains a transition $q\xrightarrow{a:b}q'$. Its successor is determined by four cases: 1. If $a\neq\epsilon$ and $b\neq\epsilon$, require $i<n$, $j<m$, $a=x_{i+1}$, and $b=y_{j+1}$; then move to $\langle q',i+1,j+1\rangle$. 2. If $a\neq\epsilon$ and $b=\epsilon$, require $i<n$ and $a=x_{i+1}$; then move to $\langle q',i+1,j\rangle$. 3. If $a=\epsilon$ and $b\neq\epsilon$, require $j<m$ and $b=y_{j+1}$; then move to $\langle q',i,j+1\rangle$. 4. If $a=b=\epsilon$, move to $\langle q',i,j\rangle$ without a symbol check. A transition is unavailable when its required bound or symbol check fails. Thus, no search edge reads beyond either string or consumes a mismatching symbol. The initial configuration is $\langle q_0,0,0\rangle$. A configuration is accepting just in case it has the form $\langle q,|x|,|y|\rangle$ with $q \in F$. We can search the finite graph of configurations with the same depth-first or breadth-first procedures we used for FSAs. Backpointers recover the paths. Why is this search correct? A configuration $\langle q,i,j\rangle$ should be reachable if and only if $T$ has a path from $q_0$ to $q$ whose input label is $x_1\ldots x_i$ and whose output label is $y_1\ldots y_j$. This is the **configuration invariant**. The initial configuration satisfies it using the length-zero path. Each search edge follows one FST transition, checks any non-epsilon label against the next symbol on the corresponding tape, and advances exactly the indices whose symbols were consumed. So every configuration added by the search has a witnessing path. Conversely, the next transition on any path with the required labels passes those same checks, so the search includes it. Induction on path length gives both directions. At an accepting configuration, the invariant says that the corresponding path has consumed all of $x$ and all of $y$ and ends in a final state. This is exactly the definition of $\langle x,y\rangle\in\mathbb{R}(T)$. Thus, reaching an accepting configuration is sound and complete for pair recognition. There are at most $|Q|(|x|+1)(|y|+1)$ configurations. Even when the transducer has epsilon cycles, memoizing visited triples thus makes the recognition search finite. Backpointers can compactly record multiple successful paths; as with FSA parsing, explicitly enumerating paths may still be infinite when a cycle can be traversed arbitrarily many times. For transduction, we do not know $y$ in advance, but every transition must still match the fixed input $x$. A configuration instead records the output produced so far: $$\langle q,i,u\rangle,$$ where $u \in \Gamma^*$. From $\langle q,i,u\rangle$, a transition $q\xrightarrow{a:b}q'$ is available only if either (i) $a=\epsilon$, or (ii) $i<|x|$ and $a=x_{i+1}$. In the first case set $i'=i$; in the second set $i'=i+1$. Set $u'=u$ when $b=\epsilon$ and $u'=ub$ otherwise, and move to $\langle q',i',u'\rangle$. Every accepting configuration with $i=|x|$ contributes its $u$ to $T(x)$. These checks ensure that each reported output is paired with the requested input rather than with some other path label. ## Epsilon cycles The transduction search need not be finite. If a reachable cycle consumes no input but produces output, a fixed input may have infinitely many outputs. Even an $\epsilon:\epsilon$ cycle can cause a naive path enumerator to revisit the same configuration forever. So a terminating implementation must handle two cases. First, both searches maintain a visited set of complete configurations. For pair recognition, the key is $\langle q,i,j\rangle$; for transduction, it is $\langle q,i,u\rangle$. Memoization makes an $\epsilon:\epsilon$ self-loop harmless because it reproduces a configuration that has already been processed. Second, memoization alone does not terminate every transduction. A cycle labeled $\epsilon:a$, for instance, reaches the distinct configurations $\langle q,i,a\rangle$, $\langle q,i,aa\rangle$, and so on. The bounded homework API thus imposes the **input-epsilon acyclicity condition** (IEAC): no cycle that is reachable from the initial state and can reach a final state may consist entirely of transitions whose input label is $\epsilon$. This condition excludes both productive $\epsilon:a$ cycles and nonproductive $\epsilon:\epsilon$ cycles; the visited set remains necessary as a defensive check for repeated configurations. An unrestricted implementation must instead bound output length or return a symbolic representation of the infinite output language. Two one-state machines expose the distinction. An $\epsilon:\epsilon$ self-loop makes a naive path search diverge but produces only the repeated configuration $\langle q,0,\epsilon\rangle$, which memoization suppresses. An $\epsilon:a$ self-loop produces $a^r$ for every $r\geq0$, so no finite explicit enumeration can return all outputs; IEAC rejects that transducer for the bounded API. ::: {.callout-caution} ## Question Can a functional FST have more than one successful path for the same input? ::: ::: {.callout-tip collapse=true} ## Answer Yes. Functionality constrains outputs, not paths. Several paths may consume the same input as long as they all produce the same output. ::: The unweighted algorithms treat every successful path alike. In [weighted automata](weighted-fsas-and-hmms.qmd), the forward algorithm sums over those paths, while the Viterbi algorithm finds the least-cost or highest-probability one [@rabiner_tutorial_1989].