Prove that, every language defined by regular expression is also defined by a finite automata.

Proof: We show by induction on the number of operators in the regular expression r that there is an NFA M with ϵ-transitions, having one final state and no transitions out of this final state, such that L(M) = L(r).

Basis (Zero operation): The expression r must be ϵ, φ or a for some a in Σ. The NFA’s clearly satisfy the conditions in fig (a), (b), (c):