Problem solving.

The following problem was taken from A3, it is number 3 on the assignemnt.

The language defined by L(R), where R is a regular expression that does not include a Kleene star, is a finite language.

1. UNDERSTANDING THE PROBLEM

The problem is asking to prove that if the condition( R is a regular expression that does not include a kleen star) is true, then the language L(R) must be finite.


2. DEVISING A PLAN

Looking at this at first sight, it appears like it would be easily solved using structural induction, so I will right out the outline of the proof and solve it.


3. CARRYING OUT THE PLAN

Basis:
If R is a regular expression, by definition then either R = \phi or R = \empty string or R = a, for some a \in \Sigma.
L(\phi) = \phi (the empty language, consisting of no strings)
L(\epsilon) = \empty string (the language consisting of just the empty string)
For any a \in \Sigma, L(a) = {a} (the language consisting of the one-symbol string a)

Induction Step:

Suppose S and T are two regular expressions that do not contain
Kleene stars, and that they denote finite languages L(S) and L(T).
Then (S+T) denotes the union L(S) u L(T), and its length is no
longer than the length of L(S)+L(T),which is a finite number.
Also (ST) denotes the concatenation L(S)L(T), and is no longer than
the length of L(S) x L(T), again a finite number(a mutiple of finite numbers).

Thus, both (S+T) and (ST) denote finite languages and all regular expressions
that do not include the Kleene star denote finite languages.

4. Looking Back

Looking back at my solution, I dont think there is any easier way to do this, and first looking at the problem I knew it must be true.