# Clarifying Practicality and Usage of a DFA's Accepted Language

I was reading up on DFA's and their accepted languages when I stumbled across this:

Let a DFA $$M$$ accept the language $$L⊆Σ^∗$$, DFA $$M'$$ accepts $$P(L)=$$ {$$w∈Σ^∗|wy∈L$$ for some $$y∈Σ^∗$$}.

Since any $$wy$$ has to be an element of $$L$$ in order for $$w$$ to be an accepted string, and $$L⊆Σ^∗$$, then wouldn't all states be accepted by $$M'$$?

For example, for machine $$M'$$ with the alphabet $$Σ=$$ {$$0,1$$}, let $$w=01$$. Since all values of $$y$$ also have to be in the alphabet $$Σ^∗$$, $$w$$ would have to be accepted. Let $$y=10$$, $$wy=0110$$, which is in the alphabet $$Σ^∗$$. Similarly, let $$y=110$$, $$wy=01110$$, which is again in the alphabet $$Σ^∗$$.

The text mentioned some transition from $$M$$ to $$M'$$, but what would the use of $$M'$$ actually be? How is it any different than, say, $$L=$$ {$$w∈Σ^∗$$}? Would they share the same finite-state diagram?

## 1 Answer

Picture the DFA $$M$$ as a directed graph, as the usual graphical depiction. Then the final states of your $$M'$$ that accepts prefixes of the language accepted by $$M$$ will have all states from which a final state of $$M$$ can be reached as final states. It should be clear that not all states of $$M$$ qualify. In particular, any dead states of $$M$$ (non-final states that loop back on all symbols) won't be final in $$M'$$.