Problem Solving Episode

So here goes my problem solving episode:

Question is Q3 from A3.


Prove that any regular expression that doesn't include a Kleene star denotes a 􏰀nite language.

1. UNDERSTANDING THE PROBLEM

We are supposed to prove that any regular expression that does not contain a * denotes a finite language. This sounds rather straightforward but it's difficult to put in words. The data we have is a regex and finite language. Condition is that any regex that does not contain a * denotes a finite language. We can easily satisfy the condition by assuming a regex without a *. The unknown is the language that we have to show is finite. Condition should be able to determine the unknown.

2. DEVISING A PLAN

First, a regex can be connected to a language. regex denotes a set of strings, just like a language by definition. So a string is made up of a finite number of symbols. Then the plan is to link the finite number of symbols to a string and this can be linked to a regex and then a language. But is this correct? The post on the bulletin board gave some crucial hints.

Seems like we can use structural induction to carry out this proof. We can start from the basic set and show that it satifies the condition that regexes without * will denote a finite language. Then we can carry on to say that 2 regexes that do not contain * will also denote 2 finite languages.

3. CARRYING OUT THE PLAN
Basis will be to show that a regex without a * will denote a finite language. We can use one symbol to show that it denotes a language with just 1 element. So it will be finite.
Then for the induction step: We can show that if 2 regexes(R,S) denotes 2(L(R),L(S)) languages, then by the IH, it will be finite as well. We shall make use of the properties of languages that L(R+S) = L(R) U L(S) and L(RS) = L(R)L(S). So since L(R)+L(S) and L(R)xL(S) are both finite, then we can conclude that any regex that does not contain * will denote a finite language.

4. Looking Back
By using structural induction, we started from the basic set and showed that it's true. Since by making use of the properties of L, structural induction is a powerful tool to show that L1+L2 contains what the IH showed. So this argument should make some sense. Not too sure if there is another way to solve this problem though.

We might also want to try to use the fact that a string is made up of a finite number of symbols and if we can link that fact to regexes without * and ultimately we might be able to use that to denote a finite language.

This concludes my problem solving episode!