A3

Since it's the last day for the Slog, I assume it's ok to now post the entry I wrote a couple of weeks ago about A3. Also, I figure no one will find this anyways. The email said we couldn't post it on the bulletin board :p

I wanted to work through Question 3, something I had my doubts about.

The question was to prove that for any Regular Expression that does not include a kleene star (*), denotes a finite language. I felt that while the question seemed obvious, it was difficult to prove.
After spending a long time thinking of a decent way to prove it (procrastinating by working through problem 3), I had an idea. I won't give the direct proof, just the outline of what I did.

I devised a plan to literally break it down into smaller (finite) elements.

I thought that if a Regular Expression R is defined by structural induction, then there must be a way to break do break R down into smaller Regular Expressions such that:

R = (R_1)(R_2)...(R_n) for all n in the natural numbers n.

Now, if R did not include a kleene star, then obviously the smaller (R_n)s do not either.
Thus, since we are using our alphabet of /Sigma = {0,1}, each of those regular expressions (R_n) must be either: the empty expression, /epsilon, 0, 1, or (1 + 0).

Each of these regular expressions themselves denote a finite language with a length <= 1. Thus, R altogether must be of length <= n. This means that there is a finite length we can assign to strings denoted by the language R.

Thus, with our finite language /Sigma = {0, 1}, our worst case string for a regular expression of length n is that the string is of length n. Since we have two characters in our alphabet, the number of combinations of those two characters is 2^n.

Depending on the length of R, we can see a finite number of strings that R can denote, thus L(R) denotes a finite language.

The only way for R to denote an infinite language is for one of those smaller RegExes (R_n) to contain.. on let's say.. a kleene star.