Indeed, there is an elegant way to compute this.
The process of finding the language accepted by an automaton $A = (Q,\Sigma, \delta, q_0, F)$ involves solving a system of equations over the monoid $(\Sigma, \circ, \epsilon)$ with $\epsilon$ denoting the empty word of the alphabet.
Denote as $\Xi_i$ the language recognized by the automaton $(Q, \Sigma, \delta, q_i, F)$ and $Q= \left\{q_0,..,q_n \right\}$.
That is, create for each state of the initial automaton a new automaton with an initial state $q_i$, for $i=0,1,..,n$. Now denote $L_{ij}$ the language consisting of all the letters on the diagram of $A$ that start from $q_i$ and end at $q_j$. So from there there is the system
$$\Xi_i = \bigcup L_{ij} \Xi_j \cup Mi$$
where $M_i = \emptyset$ if state $i$ is not final, ${\epsilon}$ otherwise.
So to find the language of the automaton $A$ we got to solve the above system of equations and find $\Xi_0$ under the operations defined by the monoid.
To solve this system we can use the following lemma:
Lemma: Let $L.M \subset \Sigma^*$ languages. The smallest language satisfying the equation
$$Z = LZ \cup M$$ is $L^* M$.
For example consider the automaton:
$A = (\left\{q_0,q_1,q_2\right\},\left\{a,b \right\},\delta, q_0,\left\{q_2 \right\})$ with the state diagram of $\delta$ as follows
The system of equations is
$$\begin{cases}
\Xi_0 = a \Xi_0 \cup b \Xi_1
\\ \Xi_1 = b\Xi_0 \cup a \Xi_2
\\ \Xi_2 = (a \cup b) \Xi_0 \cup \left\{\epsilon \right\}
\end{cases} $$
With substitution we obtain
$$\begin{cases}
\Xi_0 = a \Xi_0 \cup b \Xi_1
\\ \Xi_1 = b \Xi_0 \cup a ((a \cup b) \Xi_0 \cup \left\{\epsilon \right\})
\end{cases} $$
$$\begin{cases}
\Xi_0 = a \Xi_0 \cup b \Xi_1
\\ \Xi_1 = b \cup a ((a \cup b)) \Xi_0 \cup a)
\end{cases} $$
Substituting to the first equation we get
$$
\Xi_0 = a \Xi_0 \cup b ((b \cup a ((a \cup b)) \Xi_0 \cup a)
$$
$$
\Xi_0 = a \cup (b^2 \cup b a^2 \cup b a b) \Xi_0 \cup ba
$$
Finally, applying our lemma
$$
\Xi_0 = (a \cup b^2 \cup b a^2 \cup b a b)^* ba
$$
Thus the language accepted by the automaton is
$$L(A) = (a \cup b^2 \cup b a^2 \cup b a b)^* ba $$ as one can validate easily.
We need to remember if there was carry bit, and if word we read so far is correct. So, 3 states will be enough: valid without carry bit ($a$), valid with carry bit ($b$), invalid ($c$). Initial state is $a$, accepting state is also $a$.
If we read $n$ bits so far, giving number $x$ in the first row, $y$ in the second and $z$ in the third, automaton will be in state $a$ iff $x + y = z$, in state $b$ iff $x + y = 2^n + z$, and in $c$ otherwise.
Transitions are pretty straightforward:
- anything from $c$ goes to $c$
- $000$ transitions $a$ to $a$, and $b$ to $c$
- $001$ transitions $a$ to $c$ and $b$ to $a$
- $010$ transitions $a$ to $c$ and $b$ to $b$
- $110$ transitions $a$ to $b$ and $b$ to $c$
- $111$ transitions $a$ to $c$ and $b$ to $b$
and so on.
In general, if we read $uvw$ and assume $p = 0$ if state was $a$ and $p = 1$ if it was $b$, we need to check $w = u \oplus v \oplus p$ (if not - move to $c$), and move to $a$ if $u + v + p < 2$ and to $b$ otherwise.
Best Answer
You can use almost the same automaton for $K$, changing just which states are accept. State $x$ will be accept state for new automaton iff $\delta(x, a)$ is accept state for old automata.
Assume word $va \in L$. Then original automaton accepts this word in some state $y$, and after reading $v$ it will in in state $x$ s.t. $\delta(x, a) = y$ - so $x$ will be accept state for new automaton. Thus new automaton accepts all words $v$ s.t. $va \in L$.
Now, assume new automaton accepts word $v$ in state $x$. Then $\delta(x, a)$ is accept state in old automaton, so old automaton accepts $va$. Thus if new automaton accepts word $v$, then $va \in L$.