7. NFA Example 2

NFA Example 2

Given the following transition table:

	$0$	$1$	$ϵ$
$s$	$s,p$	$q$	$p$
$q$	$p$	$-$	$-$
$p$	$-$	$q$	$-$

Produces the NFA:

digraph {
	rankdir=LR
	init[shape=point]
	node[shape=doublecircle]; q;
	node[shape=circle];
	init->s
	
	s->s [label=0]
	s->p [label=0]
	s->q [label=1]
	s->p [label=ε]
	q->p [label=0]
	p->q [label=1]
}

$$11\text{ is rejected}\leftarrow \{\begin{array}{ll}(s,11),(q,1)& \text{stuck}\\ (s,11),(p,11),(q,1)& \text{stuck, no more}\end{array}$$ $$00\text{ is rejected}\leftarrow \{\begin{array}{ll}(s,00),(s,0),(s,ϵ)& \\ (s,00),(s,0),(s,ϵ),(p,ϵ)& \\ (s,00),(s,0),(s,ϵ)& \\ (s,00),(s,0),(p,0)& \text{stuck}\\ (s,00),(p,0)& \text{stuck}\\ (s,00),(p,00)& \text{stuck, no more}\end{array}$$ $$001\text{ is accepted}\leftarrow \{\begin{array}{ll}(s,001),(s,01),(s,1),(q,ϵ)& \text{favourable state}\\ \cdots & \end{array}$$