1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.