Another method, not covered by the answers above, is *finite automaton transformation*. As a simple example, let us show that the regular languages are closed under the *shuffle* operation, defined as follows:

$$

L_1 mathop{S} L_2 = { x_1y_1 ldots x_n y_n in Sigma^* : x_1 ldots x_n in L_1, y_1 ldots y_n in L_2 }

$$

You can show closure under shuffle using closure properties, but you can also show it directly using DFAs. Suppose that $A_i = langle Sigma, Q_i, F_i, delta_i, q_{0i} rangle$ is a DFA that accepts $L_i$ (for $i=1,2$). We construct a new DFA $langle Sigma, Q, F, delta, q_0 rangle$ as follows:

- The set of states is $Q_1 times Q_2 times {1,2}$, where the third component remembers whether the next symbol is an $x_i$ (when 1) or a $y_i$ (when 2).
- The initial state is $q_0 = langle q_{01}, q_{02}, 1 rangle$.
- The accepting states are $F = F_1 times F_2 times {1}$.
- The transition function is defined by $delta(langle q_1, q_2, 1 rangle, sigma) = langle delta_1(q_1,sigma), q_2, 2 rangle$ and $delta(langle q_1, q_2, 2 rangle, sigma) = langle q_1, delta_2(q_2,sigma), 1 rangle$.

A more sophisticated version of this method involves *guessing*. As an example, let us show that regular languages are closed under *reversal*, that is,

$$ L^R = { w^R : w in Sigma^* }. $$

(Here $(w_1ldots w_n)^R = w_n ldots w_1$.) This is one of the standard closure operations, and closure under reversal easily follows from manipulation of regular expressions (which may be regarded as the counterpart of finite automaton transformation to regular expressions) – just reverse the regular expression. But you can also prove closure using NFAs. Suppose that $L$ is accepted by a DFA $langle Sigma, Q, F, delta, q_0 rangle$. We construct an NFA $langle Sigma, Q’, F’, delta’, q’_0 rangle$, where

- The set of states is $Q’ = Q cup {q’_0}$.
- The initial state is $q’_0$.
- The unique accepting state is $q_0$.
- The transition function is defined as follows: $delta'(q’_0,epsilon) = F$, and for any state $q in Q$ and $sigma in Sigma$, $delta(q’, sigma) = { q : delta(q,sigma) = q’ }$.

(We can get rid of $q’_0$ if we allow multiple initial states.) The guessing component here is the final state of the word after reversal.

Guessing often involves also verifying. One simple example is closure under *rotation*:

$$ R(L) = { yx in Sigma^* : xy in L }. $$

Suppose that $L$ is accepted by the DFA $langle Sigma, Q, F, delta, q_0 rangle$. We construct an NFA $langle Sigma, Q’, F’, delta’, q’_0 rangle$, which operates as follows. The NFA first guesses $q=delta(q_0,x)$. It then verifies that $delta(q,y) in F$ and that $delta(q_0,x) = q$, moving from $y$ to $x$ non-deterministically. This can be formalized as follows:

- The states are $Q’ = {q’_0} cup Q times Q times {1,2}$. Apart from the initial state $q’_0$, the states are $langle q,q_{curr}, s rangle$, where $q$ is the state that we guessed, $q_{curr}$ is the current state, and $s$ specifies whether we are at the $y$ part of the input (when 1) or at the $x$ part of the input (when 2).
- The final states are $F’ = {langle q,q,2 rangle : q in Q}$: we accept when $delta(q_0,x)=q$.
- The transitions $delta'(q’_0,epsilon) = {langle q,q,1 rangle : q in Q}$ implement guessing $q$.
- The transitions $delta'(langle q,q_{curr},s rangle, sigma) = langle q,delta(q_{curr},sigma),s rangle$ (for every $q,q_{curr} in Q$ and $s in {1,2}$) simulate the original DFA.
- The transitions $delta'(langle q,q_f,1 rangle, epsilon) = langle q,q_0,2 rangle$, for every $q in Q$ and $q_f in F$, implement moving from the $y$ part to the $x$ part. This is only allowed if we’ve reached a final state on the $y$ part.

Another variant of the technique incorporates bounded counters. As an example, let us consider change *edit distance closure*:

$$ E_k(L) = { x in Sigma^* : text{ there exists $y in L$ whose edit distance from $x$ is at most $k$} }. $$

Given a DFA $langle Sigma, Q, F, delta, q_0 rangle$ for $L$, e construct an NFA $langle Sigma, Q’, F’, delta’, q’_0 rangle$ for $E_k(L)$ as follows:

- The set of states is $Q’ = Q times {0,ldots,k}$, where the second item counts the number of changes done so far.
- The initial state is $q’_0 = langle q_0,0 rangle$.
- The accepting states are $F’ = F times {0,ldots,k}$.
- For every $q,sigma,i$ we have transitions $langle delta(q,sigma), i rangle in delta'(langle q,i rangle, sigma)$.
- Insertions are handled by transitions $langle q,i+1 rangle in delta'(langle q,i rangle, sigma)$ for all $q,sigma,i$ such that $i < k$.
- Deletions are handled by transitions $langle delta(q,sigma), i+1 rangle in delta'(langle q,i rangle, epsilon)$ for all $q,sigma,i$ such that $i < k$.
- Substitutions are similarly handles by transitions $langle delta(q,sigma), i+1 rangle in delta'(langle q,i rangle, tau)$ for all $q,sigma,tau,i$ such that $i < k$.