Fika's Dramatic Problem Solving Episode.

This will be my problem solving episode for the problem set 5. The problem is as follows :

Prove that if language L has a finite number of strings, then there is is some regular expression that denotes L.

After reading the statement a few times, my understanding of the problem is that we must show that a language with a certain number of strings , k , can be written with a regular expression of the form R+S , RS , or R*. But of coarse not all of the regular expressions can denote the language , so the problem was figuring out the suitable expression.

The next step in problem solving is devising a plan(s).This problem looked quite similar to the problem on page 193 of the text. The only difference is that the language in the book is defined to be infinite , rather than our finite case. So of coarse induction was the obvious way to proceed. By assuming that a language with k strings can be denoted by a regular expression , we could prove for a language with k + 1 strings. So using simple induction seemed like the ideal way to go , as it proved an important result in the base cases, which we will need and use later in the induction step. Complete induction could also have been used to prove this statement, but in simple induction I could easily the logic of combining regular expressions of a Language with k strings and a Language with 1 string.

Now to carry out my plan to prove the statement with simple induction. Of coarse when using simple induction we prove the base cases first. Since the cases where language is empty ,the language contains epsilon (the empty string) and a language with only 1 string are the interesting cases,I proved them in the base case. In the induction step, we assume that a language (L) with k strings can be denotes by the regular expression R. Now by constructing a new language with the language L , and an element x , we can create a language with k+1 strings. We know that L' = L + x , so we know that L' can be denoted by a regular expression R for the language L and a regular expression that denotes a string x, which by our base case we know exists. So by using our induction hypothesis , and our base case , we can construct L' by the regular expressions that denote L and the string x. Thereby proving that a language consisting of k+1 strings can be denoted by a regular expression.

Looking back at the problem, it was obvious that I could've proven the statement by using complete induction , or even structural induction. But I am confident that my solution is correct and using test languages , I could see that the union of regular expressions can denote any finite ( or infinite) language because by breaking the language into two pieces , I can create a regular expression for each portion of the language.

Perhaps this wasn't as dramatic as I first thought it would be , but I hope this gives the viewer some understand of the concept and I hope my solution didn't confuse anyone. This concludes the Dramatic Problem Solving Episode.