Every language defined by a regular expression is also defined by a finite automaton

The proof is by the principle of induction on the total number of characters in a regular expression R. By ‘character ‘ we mean elements of å, Î, f, * and + .

Let the number of characters in R be 1. Then R=f or R=Î or R=a, a Î å

Accepting Î Accepting f Accepting a

Assume the theorem is true for regular expressions with n characters or less. To prove that it is true for n+1 characters let rR have n+1 characters. Then

R=P+Q or

R=PQ or

R=P*

Where P and Q are regular expressions of n characters or less. By induction hypothesis P and Q can be recognized by finite automata's as shown in figure.

P+Q

PQ

P*

Example - conversion of regular expression to FA

Previous Section HOME Next Section