Given a regular language L, prove or disprove L' is regular

Question

Given $NFA$ $N$ , $L(N)$ regular language and two words $w1$,$w2$ $\in$ $\sum^*$ such that $w1$ $\neq$ $w2$. I have to prove or disprove that

$L'=$ {$z\in \sum^*|\exists$ $w1,w2$ :$w1z$ $\in$ $L(N)$ $\wedge$ $w2z$ $\notin$ $L(N)$} is regular.

I believe this is correct but I'm having a hard time proving it. Any help will do. Thanks in advance.

Answer 1

The automaton $A$ for $L'$ can work like this:

1. Without reading any input, it guesses a $w_1$ and simulates $N$ on this string. The guessing is done letter by letter with $\lambda$-transitions. The states in which $N$ ends after reading $w_1$ is remembered.
2. $A$ guesses a $w_2$ and simulates $N$ on this string. The guessing is again done letter by letter with $\lambda$-transitions. The states in which $N$ ends after reading $w_2$ is remembered.
3. Now $A$ reads the input $z$ and simulates two cmputations of $N$ in parallel: that of $w_1z$ and that of $w_2z$. If the former ends in some final state while the latter does not, $A$ accepts.

For fixed $w_1$ and $w_2$ you could do the same without the guessing. However, it would be more efficient to do the simulations of $N$ once on paper and let $A$ start from there directly.