1

For a DFA, the definition of the transition function for a string is:

$$ \widehat{\delta}:Q\times\Sigma^\star\to Q $$

The first part (before the arrow) defines all combinations of all strings with all states by using the cartesian product. Each one of those combinations can result in change of the state of the machine. This is the part behind the arrow.

I'm having a hard time understanding first part of the transition function for a string for a NFA. My book says the definition is: $$ \widehat{\delta}:2^Q\times\Sigma^\star\to 2^Q $$ I understand the part behind the arrow, which indicates that because we're talking about an NFA, multiple changes of state can be possible given a string. The set of those possibly, multiple states are a subset of Q and thus member of the power set of Q.

Ruben23630
  • 83

2 Answers2

1

The transition function for a string in case of NFA is $$\hat{\delta}:Q\times \Sigma^*\rightarrow 2^Q$$ which indicates that for a NFA in state $q\in Q$ and an input string $w\in \Sigma^*$, the NFA may transition to more than one state and hence it takes its values on the power set of $Q$.

The extension may also take place on the set of states so that the transition function will be $$\overline\delta:2^Q\times\Sigma^*\rightarrow 2^Q$$ which for some $A\in 2^Q$ evaluates to $$\overline\delta(A, w)=\bigcup_{p\in A}\hat\delta(p, w).$$

Prajwal Kansakar
  • 5,391
  • So the definition of the transition function of a NFA given to me was just wrong? – Ruben23630 Apr 14 '17 at 11:06
  • Some authors do extend the transition from $Q$ to $2^Q$ as well. See edited answer above. – Prajwal Kansakar Apr 14 '17 at 11:15
  • Yes it's quite common in mathematics to redefine a function with the same name but working on the power set of the domain and image using $f(A) ={ \bigcup_{a \in A} f(a) }$. If your initial function is multi-valued, it makes even more sense. – Lærne Apr 14 '17 at 11:46
0

I believe the transition function for NFA will be like this : δ: Q×(Σ⋃{ε})→(Q)={R | R⊆Q} Since the empty string (ε) does not belong to any Alphabet set Therefore the the alphabet of a NFA should be the union of the alphabet and the epsilon

Jun Wang
  • 1