Automata | Proving that if $L$ is regular then $L'$ (word in $L'$ is a word from $L$ without the first and the last letter) is regular too.

I've see couple of approaches to this kind of questions yet I have no clue how to approach this one.

Let $$L$$ be a regular language and then let $$L'$$ be: $$L' = \{w \in \Sigma^\star : awb \in L, a \in \Sigma, b \in \Sigma \}$$ (word in $$L'$$ is a word from $$L$$ without the first and the last letter). Prove that if $$L$$ is regular then $$L'$$ is regular too.

I tried to make a new DFA inherited from DFA that accepts words in $$L$$ but I'm stuck on how to do this. Any help appreciated :)

• can you show that, for fixed $a \in \Sigma, b \in \Sigma$, the language $\{w \in \Sigma^\star : awb \in L\}$ is regular? Then $L'$ is the union of those Mar 7, 2021 at 12:15
• yes, I guess that makes sense... but the trouble is that i don't know exactly how to construct DFA that gets rid of the first and the last lettter, but I will think of that in that way, thanks:) Mar 7, 2021 at 12:21

SKETCH: Start with a DFA $$M$$ for $$L$$. Let $$q_0$$ be the initial state of $$M$$, let $$Q_1$$ be the set of states of $$M$$ that can be reached from $$q_0$$ in one transition, and let $$Q_a$$ be the set of states of $$M$$ that have at least one transition to an acceptor state of $$M$$. Modify $$M$$ as follows to get an NFA $$M'$$:
• Change each transition $$q_0\overset{x}\longrightarrow q$$ with $$q\in Q_1$$ to an $$\epsilon$$-transition $$q_0\overset{\epsilon}\longrightarrow q$$.
• Let $$Q_a$$ be the set of acceptor states of $$M'$$.
Then show that the NFA $$M'$$ accepts $$L'$$.
• Thank you for the response. I don't fully understand why $Q_a$ should have at least one transition to an acceptor state. Should'nt it be exactly one transition? Mar 8, 2021 at 7:46
• @quickMaths: No, as long as there is at least one transition out of $q$ to an acceptor state, we know that a word that takes $M$ to $q$ can be completed to a word of $L$ by adding one more character. Possibly this can happen in several different ways several different acceptor states, but that doesn’t matter; what matters is that it can happen in at least one way. Mar 8, 2021 at 7:50