7. Regex to NFA Example 1

Example 1

Apply the proecdure to the regular expression $((a\cup ab{)}^{\ast }ba{)}^{\ast }$. We construct step-by-step an NFA $A$ such that:

$$L(A)=\text{Language\_of}(((a\cup ab{)}^{\ast }ba{)}^{\ast })$$

Step $0$: automata accepting $\text{Language\_of}(a)$ and $\text{Language\_of}(b)$

digraph {
	rankdir=LR
	init[shape=point]
	node[label="" shape=doublecircle color=purple] a;
	node[shape=circle color=""] s;
	init->s
 
	s->a [label=a]
}
 
digraph {
	rankdir=LR
	init[shape=point]
	node[label="" shape=doublecircle color=purple] a;
	node[shape=circle color=""] s;
	init->s
 
	s->a [label=b]
}

Step $1$: automata accepting $\text{Language\_of}(ab)$ and $\text{Language\_of}(ba)$

digraph {
	rankdir=LR
	init[shape=point]
	node[label="" shape=doublecircle color=purple] b;
	node[shape=circle color=""] s;
	init->s
 
	s->a [label=a]
	a->b [label=b]
}

digraph {
	rankdir=LR
	init[shape=point]
	node[label="" shape=doublecircle color=purple] b;
	node[shape=circle color=""] s;
	init->s
 
	s->a [label=b]
	a->b [label=a]
}

Step $2$: automaton accepting $\text{Language\_of}(a\cup ab)$

digraph {
	rankdir=LR
	init[shape=point]
	node[label="" shape=doublecircle color=purple] b,j;
	node[shape=circle color=""] s;
	init->g
 
	s->a [label=a]
	a->b [label=b]
	
	g->s [label=ε]
	g->h [label=ε]
	h->j [label=a]
}

Step $3$: automaton accepting $\text{Language\_of}((a\cup ab{)}^{\ast })$

digraph {
	rankdir=LR
	init[shape=point]
	node[label="" shape=doublecircle color=purple] k;
	node[shape=circle color=""] s;
	init->k
 
	k->g [label=ε]
 
	s->a [label=a]
	a->b [label=b]
	
	g->s [label=ε]
	g->h [label=ε]
	h->j [label=a]
	
	b->k [label=ε]
	j->k [label=ε]
}

Step $4$: automaton accepting $\text{Language\_of}((a\cup ab{)}^{\ast }ba)$

digraph {
	rankdir=LR
	init[shape=point]
	node[label="" shape=doublecircle color=purple] m;
	node[shape=circle color=""] s;
	init->k
 
	k->g [label=ε]
 
	s->a [label=a]
	a->b [label=b]
	
	g->s [label=ε]
	g->h [label=ε]
	h->j [label=a]
	
	b->k [label=ε]
	j->k [label=ε]
	
	k->n [label=b]
	n->m [label=a]
}

Step $5$: automaton accepting $\text{Language\_of}(((a\cup ab{)}^{\ast }ba{)}^{\ast })$

digraph {
	rankdir=LR
	init[shape=point]
	node[label="" shape=doublecircle color=purple] m;
	node[shape=circle color=""] s;
	init->k
 
	k->g [label=ε]
 
	s->a [label=a]
	a->b [label=b]
	
	g->s [label=ε]
	g->h [label=ε]
	h->j [label=a]
	
	b->k [label=ε]
	j->k [label=ε]
	
	k->n [label=b]
	n->m [label=a]
}