Measuring the difficulty of a sequence-to-sequence problem using automata theory Automata theory measures the difficulty of language recognition problems by using an automaton that can accept or reject for the given string.
However, I want to measure the difficulty of a sequence-to-sequence (seq2seq) problem.
For instance, what is the difficulty of the following seq2seq problem associated with counting as follows:
$\Sigma = \{a, b, 1, 2, 3, T \}$ where $T$ is a terminal symbol.
$A = \{xT \}_{x \in \{a1, a2, a3, b1, b2, b3\}^*}$
$B = \{sT \}_{s \in \{a, b\}^*}$
A seq2seq function $f:A \to B: w_1d_1 \cdots w_nd_n T \mapsto \underbrace{w_1 \cdots w_1}_{d_1} \cdots \underbrace{w_n \cdots w_n}_{d_n}T$ where $w_i \in \{a, b\}$ and $d_i \in \{1, 2, 3\}$.
To go further, is there any way to convert a seq2seq problem into a language recognition problem?
Moore machine or Mealy machine equipped with an output function deals with similar problem where  the length of the output is equal or less than that of the input.
Finite-state transducers capture a class of seq2seq problems that correspond to the notion of regular languages, which could be thought of as the &quot;easiest&quot; problems in automata theory.  Your example function $f$ can be implemented by a finite-state transducer.