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.

Question

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 :)

Answer 1

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