NFSA revisit.

NFSA is not yet covered in any assignment or problem set, yet it is among the test and exam material. So here i do a little review:

Intuitively, DFSA is the sort of FSA that if the current state and the next character in the string are known, we know there is one and only one state to go next. In the contrary, for NFSA each state and corresponding next character combination has multiple choices to the next state. Whats more state transition can even go without the next character, called /epsilon transition. Obviously, for a specific string, there will be a number of state transition routes, each might lead to different end state. To deal with this, if any of these routes eventually lead to a accepting state, the string is accepted by this NFSA. Clearly, designing a NFSA is more intuitive when coping with the patterns with "+" operation.

*The mathematical definition of the NFSA is similar to those of DFSA, that M = (Q, /Sigma, /delta, s, F). Only difference being the transition function /delta, where each element will have a set of "destinations". If the NFSA includes /epsilon transition, /delta also includes transition function for that. Conversely, DFSA is a special case of NFSA.

Equivalence of NFSA and DFSA:

For an NFSA M = (Q, \sigma, \delta, s, F), converting into a DFSA M' = (Q', \sigma', \delta', s', F'):
Subset Construction: each state of M' is a set of states of M.
Q' = P(Q) (all possible subsets of the powerset of Q.)
\sigma' = \sigma (Alphabet remains same..of course so!)
s' = \epsilon(s) (states from s with \epsilon transition)
F' = {q'\in Q'|Q \intersect F not empty}
\epsilon' : the transition functions that maps the element in Q' to element in Q' with a transition.

Ex: if Q = {q0, q1}, F = q1,
then Q' can be {q'(@), q'0, q'1, q'01}, F' = {q'1,q'01}, do some combination with \epsilon'.