Equivalence of FA with Regular Expressions

We will use NFA with -transitions to show this equivalence.

Theorem: Let r be a regular expression. Then there exists an NFA with -transitions that accepts L(r).

Proof: Induction on number of operators in r.

basis:

n=0 (Zero operators)

 
Figure 10: FA's for , or , for .

Hypothesis:

Assume true for operators.

Induction:

i operators

case 1:

. Construct FA using the FA's

for regular expressions and

for . Then, for M

 
Figure 11: NFA for

Case 2:

 
Figure 12: NFA for

Case 3:

 
Figure 13: NFA for

Example: