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$ – Yuval Filmus Mar 5 '20 at 8:39
  • $\begingroup$ @YuvalFilmus I am pretty sure that it is possible $\endgroup$ – Eric Toporek Mar 5 '20 at 19:15
  • $\begingroup$ That would be an easier target, which you could start with. $\endgroup$ – Yuval Filmus Mar 5 '20 at 19:34

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, privacy policy and cookie policy

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