Every regular expression describes regular language, let R be an arbitrary regular expression over the alphabet Σ. We will prove that the language described by R is a regular language. The proof is by induction on the structure of R. The first base case of induction: Assume that R = ε.  The  R describes the language of {ε}. In order