The language accepted by an NFA

To see whether a word $w\in\Sigma^*$ is accepted by an NFA ($w\in L(A)$ we may have to use several marker. Initially we put one marker on the initial state. Then each time when we read a symbol we look at all the markers: we remove the old marker and put markers at all the states which are reachable via an arrow marked with the current input symbol (this may include the state which was marked in the previously). Thus we may have to use several marker but it may also happen that all markers disappear (if no appropriate arrows exist). In this case the word is not accepted. If at the end of the word any of the final states has a marker on it then the word is accepted.

E.g. consider the word $100$ (which is not accepted by $C$). Initially we have

After reading $1$ we have to use two markers because there are two arrows from $q_0$ which are labelled $1$:

Now after reading 0 the automaton has still got two markers, one of them in an accepting state:

However, after reading the 2nd 0 the second marker disappears because there is no edge leaving $q_2$ and we have:

which is not accepting because no marker is in the accepting state.

To specify the extended transition function for NFAs we use an generalisation of the union operation $\cup$ on sets. We define $\bigcup$ to be the union of a (finite) set of sets:

$$\bigcup \{ A_1, A_2, \dots A_n \} = A_1 \cup A_2 \cup \dots \cup A_n$$

In the special cases of the empty sets of sets and a one element set of sets we define:

$$\bigcup \{\} = \{\} \qquad \bigcup \{A\} = A$$

As an example

$$\bigcup \{\{1\},\{2,3\},\{1,3\}\} = \{1\}\cup\{2,3\}\cup\{1,3\} = \{1,2,3\}$$

Actually, we may define $\bigcup$ by comprehension, which also extends the operation to infinite sets of sets (although we don't need this here)

$$\bigcup B = \{ x \mid \exists A\in B. x\in A \}$$

We define $\hat{\delta}\in {\cal P}(Q)\times \Sigma^* \to {\cal P}(Q)$ with the intention that $\hat{\delta}(S,w)$ is the set of states which is marked after having read $w$ starting with the initial markers given by $S$.

$$\hat{\delta}(S,\epsilon) = S$$ (3)

$$\hat{\delta}(S,xw) = \bigcup \{ \hat{\delta}(\delta(q,x),w) \mid q \in S \}$$ (4)

As an example we calculate $\hat{\delta}_C(q_0,100)$ which is $\{q_0\}$ as we already know from playing with markers.

$$% latex2html id marker 4599 \begin{array}{lcl} \ \hat{\delta... ...n-delta-hat-epsilon}) twice.}}\\ & = & \{ q_0 \} \end{array}$$

Using the extended transition function we define the language of an NFA as

$$L(A) = \{ w \mid \hat{\delta}(S,w) \cap F \not= \{\} \}$$

This shows that $100\notin L(C)$ because

$$\hat{\delta}(\{q_0\},100) = \{q_0\} \cap \{q_2\} = \{\}$$