Let $L$ be a regular language on $\Sigma$ and let $M= \langle , \Sigma, \delta, , \rangle$ be a deterministic finite automaton. Define $'=\{ \mid \exists ∈\Sigma^* ∶∈\}$.
I'm trying to build a new automaton (deterministic or nondeterministic) $M'$ that accepts $L'$ and I'm trying to prove that the construction of $M'$ really accepts $L'$.
Thank you.
Let $\mathcal{A} = (Q, A, \cdot, i, F)$ be the minimal deterministic finite automaton recognising $L$. For a subset $K$ of $Q$ and a word $u \in A^*$, let $K \cdot u = \{q \cdot u \mid q \in K\}$.
One can obtain a DFA $\mathcal{A}'$ recognising $L'$ as follows. Let $\mathcal{A}' = (Q', A, \cdot, i', F')$ where $Q' = Q \times \mathcal{P}(Q)$, $i' = (i, Q)$, $F' = \{(q, S) \in Q' \mid S \cap F \not= \emptyset\}$ and, for each letter $a$ and each $(q, S) \in Q'$, $$ (q, S)\cdot a = (q \cdot a, q \cdot aA^* \cup S \cdot a). $$ Since $\mathcal{A}$ is minimal, every state is accessible, that is $i \cdot A^* = Q$. Then one gets by induction on $n$ \begin{multline*} (i, Q)\cdot a_1 \dotsm a_n = (i \cdot a_1 \dotsm a_n, {i \cdot A^*a_1 \dotsm a_n} \cup {i \cdot a_1A^*a_2 \dotsm a_n} \\ \cup {i \cdot a_1a_2A^*a_3 \dotsm a_n} \cup \dotsm \cup {i \cdot a_1 \dotsm a_nA^*}) \end{multline*} It follows that $(i, Q)\cdot a_1 \dotsm a_n \in F'$ if and only if there exist $x, z \in A^*$ such that $(i \cdot xA^*z) \cap F \not= \emptyset$, that is, there exists $y \in A^*$ such that $i \cdot xyz \in F$ or equivalently, $xyz \in L$.