5. NFAs transition table, acceptance

Nondeterminism

Apart from having a choice in certain situations, there are other permitted features in nondeterministic finite automata (NFA):

• There can be states and symbols such that no arrow labelled by that symbol leaves thes tate in question: reading that symbol in the state the device would get stuck.
• We also allow the machine to jump from a state to another state, without ‘consuming’ any input symbol from the tape (the head doesn’t move). The allowed ‘state-jumps’ will be indicated on the state transition digrams by arrows labelled by the empty word $ϵ$.

digraph {
	rankdir=LR
	init[shape=point]
	node[shape=doublecircle]; s;
	node[shape=circle];
	init->s
	
	s->q [label=ε]
	q->s [label=a]
	
	s->r [label=b]
	r->r [label=a]
	
	r->q [label=a]
	r->q [label=b]
}

NFA Transition Table

From the NFA described above, we know that the states are $s,q,r$, the input alphabet is $\{a,b\}$, the initial state is $s$ and the favourable state is $s$. We find the table:

	$a$	$b$	$ϵ$
$s$	$-$	$r$	$q$
$q$	$s$	$-$	$-$
$r$	$q,r$	$q$	$-$

This table has a few notable features:

• There can be ‘cells’ in the table containing no or more than one states.
• The table has an $ϵ$-column (for any jumps).

An NFA can be regarded as a DFA if all cells in the $ϵ$-column are empty, and in vevery other column every cell contains a single state.

Acceptance of words by NFAs

In an NFA, there can be more than one computation on an input word. Some of these may end up in a favourable state, some may not.

A word $w$ is accepted by NFA $A$ if there is a computation of $A$ on input $w$ that ends up in some favourable state.

title: There may be other bad computations.

title: Getting stuck in a favourable state may not mean acceptance. The entire word needs to be read.

In any other case, $A$ rejects the input word. So an NFA can reject an input word $w$ if every computation on $w$ is either ‘stuck’ or ends up in a non-favourable state.