Assignment 3 Question 3

In this question we (group effort) had to proof that a regular expression that doesn’t include the Kleene star would denote a finite language. The way we understood this question was that, if we include the Kleene star in our regular expression then we would have infinite repetitions of a pattern, thus consequently not a finite language. We set out to proof by simple induction that Kleene star leads to an infinite language. But this approach didn’t seem promising when we got to describing languages and alphabets. Thus we abandoned this approach and set out to proof that if the Kleene star was excluded, we would have a finite language. More specifically, if we only had union and concatenation available to our regular expression, then we would only be able to match languages consisting of finite number of strings. This approach was more plausible and was easier to carry out. We used complete induction on the sets of language, and show that the concatenation of two unions yielded a finite language.