Is there a subtle difference between NOEXTEND(A) vs NOPREFIX(A)?

1.1k Views Asked by At

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?

1

There are 1 best solutions below

2
On BEST ANSWER

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