# NFA-$\epsilon$ extended transition function for inverted strings

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?

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