8. Designing NFAs

Designing NFAs

Nondeterminism can be viewed as a sort of parallel computing model, within which several processes can be running concurrently.

NDAs are much easier to design than DFAs, whatever can be done by an NDA can also be done (in a more complicated way) in a DFA. Nondeterminism does not increase computation power of finite automata.

NFAs are used in hardware / chip design:

• Given a task, NFA is designed.
• NFA is turned into a DFA.
• Resulting DFA is ‘minimised’.
• Obtained minimal DFA is hard-wired.

Pattern Matching

Revisiting 1-3. Designing DFAs > Pattern Matching.

Design a finite automaton $A$ such that $L(A)$ consists of all the strings of $a$s and $b$s that contain $\boxed{aab}$ as a substring.

	$a$	$b$	$ϵ$
$u$	$u,x$	$u$	$-$
$x$	$y$	$-$	$-$
$y$	$-$	$z$	$-$
$z$	$z$	$z$	$-$

digraph {
	rankdir=LR
	init[shape=point]
	node[shape=doublecircle]; z;
	node[shape=circle];
	init->u
	
	u->u [label=a]
	u->u [label=b]
	u->x [label=a]
	x->y [label=a]
	y->z [label=b]
	z->z [label=a]
	z->z [label=b]
}

Given the same task, it is much easier to design an NFA than a DFA for it:

• we don’t have to worry about all computations
• we need to ensure that if a word is accepted, then there is at least one ‘good’ computation for it
• if a word should be rejected, there is no ‘good’ computation for it