5-6. Turning regular expressions to NFAs

Turning regular expressions to NFAs

1. There is a general ‘mechanical’ proecedure ${\mathcal{P}}_1$ that converts any regular expression $R$ to an NFA $A_R$ such that $L(A_R)=\text{Language\_of}(R)$. So every regular language is accepted by some automaton.
2. There is a general ‘mechanical’ procedure ${\mathcal{P}}_2$ that converts any NFA $A$ to a regular expression $R_A$ such that $\text{Language\_of}(R_A)=L(a)$. So every language that is accepted by some automaton is regular. This algorithm is out of scope.

title: Regular langauges are <u>precisely those</u> languages that are accepted by finite automata.

Procedure ${\mathcal{P}}_1$

The procedure $P_1$ which converts any regular expression $R$ to an NFA $A_R$ such that $L(A_R)=\text{Language\_of}(R)$ operates along the recursive description of the regular expression $R$.

Basis Cases

• If $R=\varnothing$ then $\text{Language\_of}(R)=\varnothing$.

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

• If $R=ϵ$ then $\text{Language\_of}(R)=ϵ$.

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

• If $R=a$ then $\text{Language\_of}(R)=a$.

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

Assumptions for recursive cases

• $\boxed{A_R}$: accepts $\text{Language\_of}(R)$

• $\boxed{A_Z}$: accepts $\text{Language\_of}(Z)$

  digraph {
    subgraph cluster0 {
    	label="R"
    	init[shape=point]
    	node[label="" shape=doublecircle color=purple] a, b;
    	node[shape=circle color=""] s, c, d;
    	init->s
    }
    
    subgraph cluster1 {
    	label="Z"
    	init2[shape=point]
    	node[label="" shape=doublecircle color=purple] f, g;
    	node[shape=circle color=""] e, h, i;
    	init2->e
    }
  }

Recursive Cases: Automaton accepting $\text{Language\_of}(R\cup Z)$ (accepted by $A_{R\cup Z}$)

digraph {
	node[label=""]
	
	init[shape=point]
		
	init->z
	z->s [label=ε]
	z->e [label=ε]
 
	subgraph cluster0 {
		label="R"
		node[label="" shape=doublecircle color=purple] a, b;
		node[shape=circle color=""] s, c, d;
	}
 
	subgraph cluster1 {
		label="Z"
		node[label="" shape=doublecircle color=purple] f, g;
		node[shape=circle color=""] e, h, i;
	}
}

Recursive Cases: Automaton accepting $\text{Language\_of}(RZ)$ (accepted by $A_{RZ}$)

digraph {
  node[label=""]
 
  subgraph cluster1 {
  	label="Z"
  	node[label="" shape=doublecircle color=purple] f, g;
  	node[shape=circle color=""] e, h, i;
  }
  
  subgraph cluster0 {
  	label="R"
  	init[shape=point]
  	node[shape=circle color=""] s, c, d;
  	init->s
  	a->e [label=ε];
  	b->e [label=ε];
  }
}

Recursive Cases: Automaton accepting $\text{Language\_of}(R^{\ast })$ (accepted by $A_{R^{\ast }}$)

digraph {
  init[shape=point];
  	
  node[label="" shape=doublecircle color=purple] w;
  init->w
  
  node[shape=circle color=""]
  w->s
  a->w
  b->w
  	
  subgraph cluster0 {
  	label="R"
  	node[shape=circle color=""] a, b, s, c, d;
  }
}