0
$\begingroup$

My question originates from Sipser's book.

Let A be a language with the DFA $(Q, \Sigma, \delta, q_{0}, F)$ and define:

NOPREFIX(A) = {w $\in$ A| no proper prefix of w is a member of A}

NOEXTEND(A) = {w $\in$ A| w is not the proper prefix of any string in A}

For NOPREFIX(A), the book provides the solution as modifying the transition function as: $\begin{equation} \delta'(r, a)=\begin{cases} \delta(r, a), & \text{$r\notin F$}\\ \emptyset, & \text{$r\in F$} \end{cases} \end{equation} $

That is, just eliminate all the transitions from the accept states.

On the other hand, the solution I have for NOEXTEND(A) is to perform DFS on all accepting states and make sure no path out of any $q\in F$ leads to any of accept states and come up with $F'\subseteq F$ that meets this criterion.

The difference between the two DFAs becomes, the while the latter allows some transitions out of an accept state, none of those can lead to an accept state. Therefore, NOEXTEND(A) and NOPREFIX(A) are, in fact, the same language.

I am concerned that I might be missing a subtle point. Could you, please, provide some hints?

$\endgroup$
1
$\begingroup$

Let $A=\left\{w\in\{a,b\}^*:|w|_b=1\right\}$; this is certainly a regular language. Then

$$\operatorname{NOPREFIX}(A)=\{a^nb:n\ge 0\}$$

and

$$\operatorname{NOEXTEND}(A)=\varnothing\;,$$

since if $w\in A$, then $wa\in A$. That is, $\operatorname{NOPREFIX}(A)$ contains precisely the words of $A$ whose single $b$ is at the end, and $\operatorname{NOEXTEND}(A)$ is empty, since every member of $A$ can be extended to another member of $A$ by appending $a$. In this case it’s very clear that they are not the same language. If you apply your approach to the minimal DFA for $A$, you’ll find that $F'=\varnothing$.

$\endgroup$
  • $\begingroup$ Thanks for the explanation. I though more about it and realized that NOEXTEND(A) is a subset of NOPREFIX(A) due to the restrictions on the accept states. $\endgroup$ – Vectorizer Jan 3 '16 at 21:35
  • $\begingroup$ @Vectorizer: You’re welcome. But consider $A=\{a,aa\}$ over the alphabet $\{a\}$: $\operatorname{NOPREFIX}(A)=\{a\}$, and $\operatorname{NOEXTEND}(A)=\{aa\}$, so it’s not quite that simple. $\endgroup$ – Brian M. Scott Jan 3 '16 at 21:38

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.