Prove that if $ L $ is a regular language over the alphabet $ Z = \{ 0,1 \} $, then $ L' = \{ax \mid x \in L \} $ is also regular for any a in $Z$.

Question

Prove that if $L$ is a regular language over the alphabet $Z = \{0,1\}$, then $L' = \{ax \mid x \in L\}$ is also regular for any $a \in Z$.

I'm not sure how to even begin on this one. If even a shred of familiarity is brought out from asking this on here, it might give me the push in the direction I desperately need.

Answer 1

There are at least three different ways to prove this:

• If $L$ is regular, then there is a regular expression that accepts $L$, name it $\alpha$. Then $a\alpha$ is the regular expressions recognizing $L'$ thus proving that it is regular.
• As pointed out by Thomas Andrews, regular languages are closed for concatenation, as $\{a\}$ and $L$ are both regular, then so is $\{a\}\cdot L$.
• Let $A$ be the deterministic automaton recognizing $L$ with initial state $I$. Then build another automaton $A'$ which looks the same as $A$, but has one more state $I'$ which will be the initial state of new automaton. The transition function is also similar to that of $A$, but from $I'$ moves on $a$ to $I$, while on $Z \setminus \{a\}$ goes to the "trash state" (if there is no trash state, you need to add it too). Then $A'$ accepts $L'$, hence it is regular.

I hope this helps ;-)