how can I prove that if I have a regular language L, that L' is a regular language

Question

how can I prove that if I have a regular language L and I create a new language L'

where L' = (L but with last letter repeated) (i.e. if ab is in language L then abb is in language L')

that L' is a regular language

I tried solving the question but I have no way of being sure of my solutions so I'll post it here:

L is a regular language therefor there is a regular expression for it, we create a new language x where x =L*($\Sigma$), $\Sigma$ is all the letters in language L ,x is a regular language because it is regular language chained with a letter ,and letters are a regular expression the language L' is a subset of x, there for x can be written as x=L' $\cup$ t (t=x/L'), and therefor L' has to be a regular expression because if it wasn't then x would not be a a regular language

Answer 1

Let $A$ be the alphabet. For each letter $a \in A$, let $$ La^{-1} = \{u \in A^* \mid ua \in L\} $$ It is a well known fact that if $L$ is regular, then so is $La^{-1}$. Now your language $L'$ can be written as $$ L' = \bigcup_{a \in A}\ (La^{-1})aa $$ For each $a \in A$, $(La^{-1})aa$ is the product of the two regular languages $La^{-1}$ and $aa$ and this is regular. It follows that $L'$ is a finite union of regular languages and this is regular.

Answer 2

Since $L$ (over some alphabet $\Sigma$) is regular, there is a finite automaton $\mathcal{M}$ that recognises $L$. We now need to try and build a finite automaton $\mathcal{M}'$ that recognises $L'$. Let $Q_F$ be the collection of all state-symbol pairs of $\mathcal{M}$ that cause a transition into any of its accept states. More formally, $$Q_F := \{(q,s)\in Q\times \Sigma : \delta(q,s) \in F\}, $$ where $\delta\colon Q\times \Sigma \to Q$ is the transition function of $\mathcal{M}$, and $F$ is the set of accept states. We add a new state $A$ to $Q$ and make this the only accept state. Next, for every pair $(q,s)\in Q_F$, we add a new state $n_{(q,s)}$, and set $\delta^+(q,s) = \{n_{(q,s)}, \delta(q,s)\}$ and $\delta^+(n_{(q,s)},s) = A$. For $(q,s)\in (Q\times \Sigma) \setminus Q_F$ we leave $\delta^+(q,s) = \delta(q,s)$.

Note that the resulting automaton is non-deterministic, but this is fine since an equivalent DFA always exists. I now leave it up to you to show that this new NDFA $\mathcal{M}' := \{Q\cup A, \Sigma, \delta^+, q_o, A \}$ recognises $L'$.