It is well known that in $NFA-\epsilon$ the extended transition function is defined as it follows: \begin{align*} \hat\delta: Q &\times \Sigma^* \rightarrow \mathbb{P}(Q) \\ \hat\delta(q,\epsilon) &= ECLOSURE(q) \\ \hat\delta(q,\alpha x) &= \bigcup_{p_i \in \hat\delta(q,\alpha)}ECLOSURE(\delta(p_i,x)) \text{ for } \alpha \in \Sigma^* \text{ and } x \in \Sigma \end{align*}

I would like to give an equivalent definition for the function but now considering an string $w \in \Sigma^* $ such that $w = x\alpha$ with the same definitions for $x$ and $\alpha$ given above. But what I've only got is the base case (i.e. $w = \epsilon$) which is pretty the same. Any hints to define the function like that?

  • $\begingroup$ Can you do it for vanilla NFAs (without $\epsilon$ moves)? $\endgroup$ Mar 5, 2020 at 8:39
  • $\begingroup$ @YuvalFilmus I am pretty sure that it is possible $\endgroup$ Mar 5, 2020 at 19:15
  • $\begingroup$ That would be an easier target, which you could start with. $\endgroup$ Mar 5, 2020 at 19:34

1 Answer 1


First, there's a typo at your definition of $\hat\delta$. Case $\hat\delta(q,\alpha x)$ should be $\bigcup_{p_i \in \hat\delta(q,\alpha)}ECLOSURE(\delta(\color{green}{p_i},x))$ (green for highlighting the difference).

The equivalent definition in terms of a string given as $(x\alpha)$, where $x\in\Sigma$ and $\alpha\in\Sigma^*$, is $$ \hat\delta(q,x\alpha) = \bigcup_{p_i \in ECLOSURE(\delta(q,x))} \hat\delta(p_i,\alpha) $$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.