How to prove that if the language L is regular , then K is also regular

Question

Let $L$ be any language over $\{a,b\}$.

Let $K$ be the language : $K=\{v:va \in L \}$

In other words, the word $v$ is in $K$ if he has the properties that if we add an $a$ at the end of $v$ we get a word of $L$

Show that if $L$ is regular then $K$ is also regular.

Watch out : Do not mistake $K$ with $L \circ\{a\} $ Example : if $L$ is represented by the regular expression $(ba)^*$ then $K$ is represented by $(ba)^*b$

So now it's said that to proove this, an option could be that we can show how we can modify an automaton that recognize $L$ to get an automaton that recognize $K$. A formal proof is not required but we have to be clear. We can also show an example.

Based on this last paragraph i started to draw an automaton for both $L$ and $K$ but i am not sure what to do next and how can this proove that $K$ is regular..

Drawing tool if u need it : http://madebyevan.com/fsm/ Thanks for your help.

Answer 1

For the language in your example there is a simpler DFA for $K$. You can use the DFA for $L$ with one simple modification: make state $2$ the acceptor state instead of state $1$. Any word that takes the DFA to state $2$ is in $K$, because adding an $a$ to the end will drive the DFA to state $1$, where the word will be accepted.

This idea works more generally. Suppose that you have a DFA $M$ for $L$, and it has a transition $q_i\overset{a}\longrightarrow q_j$, where $j$ is an acceptor state. If a word $v$ takes $M$ to state $q_i$, the word $va$ will take $M$ to state $q_j$, so $va\in L$, and $v\in K$. Thus, you want $v$ to be accepted, so you want $q_i$ to be an acceptor state in the DFA for $K$. This is true for all $a$-transitions to acceptor states of $M$: the states at the starting points of those transitions should be the acceptor states in the DFA for $K$.

Answer 2

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$.