6. NFA Example 1

NFA Example 1

Given the following NFA:

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

$$baba\text{ is accepted}\leftarrow \{\begin{array}{ll}(s,baba),(q,baba)& \text{stuck}\\ (s,baba),(r,aba),(q,ba),(q,a),(s,ϵ)& \text{favourable}\end{array}$$ $$aa\text{ is accepted}\leftarrow \{\begin{array}{ll}(s,aa),(q,aa),(s,a),(q,a),(s,ϵ)& \text{favourable}\end{array}$$ $$babba\text{ is accepted}\leftarrow \{\begin{array}{ll}(s,babba),(q,babba)& \text{stuck}\\ (s,babba),(r,abba),(r,bba),(q,ba)& \text{stuck}\\ (s,babba),(r,abba),(q,bba)& \text{stuck, no more cases}\end{array}$$