Inductive Definition of regular expression

Question

Give an inductive definition of regular expressions that do not use the star operator. Prove by induction on this definition that every such expression denotes a finite language not containing lambda.

Can someone please help me understand how to give an induction definition for this and explain how to get such an expression to denote any finite language that does not contain lambda?

Answer 1

The inductive definition is just the same that you have for regular expressions, except that now you don't want the rule for the star operator, so you don't include it in this new definition.

Now, in order to prove that every such regular expression denotes a finite language not containing $\lambda$, you need to show that:

1. All the initial regular expressions denote finite languages not containing $\lambda$, and
2. If $R,\,S$ are regular expressions denoting finite languages not containing $\lambda$, then every regular expression obtained from $R$ and $S$ using the rules still denotes a finite language not containing $\lambda$.