I'm trying to see if the language $L/w = \{x\mid wx\in L\}$ is regular given that $L$ itself is regular.

It seems to me that if $L=L(A)$ for the NFA $A = (Q, \Sigma, \delta, S, F)$, then the NFA $A'$ should accept $L/w$, where $A' = (Q', \Sigma, \delta', S', F')$. Each component is defined as:

  • $Q' = $ all states in $Q$ reachable from $S'$
  • $\delta'(q,a) = \delta(q,a)\mid_{Q'}$
  • $S' =$ the union of $\hat{\delta}(q,w)$ for all $q\in S$
  • $F' = $ the set of final states reachable from $S'$

The logic is that for some $s\in S,\exists q\in Q$ such that $s\rightarrow^{w}_{*}q$ (assuming that $L/w$ is non-empty). Then if $wx\in L$, it follows that $s\rightarrow^{w}_{A*}q\rightarrow^{x}_{A'*}f$ for some $f\in F$ and $wx$ is accepted only if $x\in A'$.

Is this construction correct?

  • 1
    $\begingroup$ I think the construction is correct. @nirshahar could you provide an example? I can not understand how you came up with your set description. Why must a potential $x$ that their construction recognizes fulfill $\forall y \in L\, y = mx$ ? The $\forall$ makes no sense to me. $\endgroup$
    – plshelp
    Oct 18 '21 at 15:24
  • $\begingroup$ My bad, I read the question incorrectly :) I thought that the NFA definition was something else, but looking at it again I see what I missed. $\endgroup$
    – nir shahar
    Oct 18 '21 at 16:30
  • $\begingroup$ Yes, seems correct. It assumes that the NFA may have several initial states, including none. (Ok with me, but not with most textbooks.) Then it would have been sufficient just to replace only the initial states $S$ by the new initial states in $S'$. No need to restrict the other components, the unreachable parts just don't change the language. $\endgroup$ Oct 18 '21 at 22:15
  • 3
    $\begingroup$ I’m voting to close this question because it is a request to check OP's answer to an exercise. $\endgroup$ Oct 19 '21 at 7:42
  • $\begingroup$ @YuvalFilmus may I ask what is wrong with checking OP's answer to an exercice as long as he did the effort to answer the question himself ? The horrible examples that must be closed are 144930 and 144926 $\endgroup$
    – user206904
    Oct 20 '21 at 0:27

Your Answer

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

Browse other questions tagged or ask your own question.