¿Existe una sutil diferencia entre NOEXTEND(A) y NOPREFIX(A)?

Question

Mi pregunta tiene su origen en el libro de Sipser.

Sea A un lenguaje con el DFA $(Q, \Sigma, \delta, q_{0}, F)$ y definir:

NOPREFIX(A) = {w $\in$ A| ningún prefijo propio de w es miembro de A}

NOEXTEND(A) = {w $\in$ A| w no es el prefijo propio de ninguna cadena en A}

Para NOPREFIX(A), el libro proporciona la solución como modificar la función de transición como: $\begin{equation} \delta'(r, a)=\begin{cases} \delta(r, a), & \text{$r\notin F$}\\ \emptyset, & \text{$r\in F$} \end{cases} \end{equation} $

Es decir, eliminar todas las transiciones de los estados de aceptación.

Por otro lado, la solución que tengo para NOEXTEND(A) es realizar DFS en todos los estados de aceptación y asegurarse de que ninguna ruta de salida de cualquier $q\in F$ lleva a cualquiera de los estados de aceptación y llega a $F'\subseteq F$ que cumple este criterio.

La diferencia entre los dos DFAs es que, mientras el último permite algunas transiciones fuera de un estado de aceptación, ninguna de ellas puede llevar a un estado de aceptación. Por lo tanto, NOEXTEND(A) y NOPREFIX(A) son, de hecho, el mismo lenguaje.

Me preocupa que pueda estar perdiendo un punto sutil. ¿Podría, por favor, darme algunas pistas?

Answer 1

Dejemos que $A=\left\{w\in\{a,b\}^*:|w|_b=1\right\}$ ; esto es ciertamente un lenguaje regular. Entonces

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

y

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

ya que si $w\in A$ entonces $wa\in A$ . Es decir, $\operatorname{NOPREFIX}(A)$ contiene precisamente las palabras de $A$ cuyo único $b$ está al final, y $\operatorname{NOEXTEND}(A)$ está vacío, ya que cada miembro de $A$ puede extenderse a otro miembro de $A$ añadiendo $a$ . En este caso está muy claro que no son el mismo idioma. Si se aplica su enfoque a la ADF mínima para $A$ , encontrará que $F'=\varnothing$ .