Problem Set 5

Although this problem set seemed trivial at first, it took me sometime to express the proof formally. The theorem was: If language L has a finite number of strings, then there is some regular expression that denotes L. Any finite set of language can be expressed by a regular expression using the union or concatenation operator. As long the theorem can be proven using one of these operators, then it would be true for all cases. I used induction on the number of strings in an arbitrary language to prove the theorem. Let the language L be {l1, l2, l3, l4}. This language can be denoted by the RE, R= l1+l2+l3+l4. If a new string (l5) is added to L, then it could be denoted by R= l1+l2+l3+l4+l5, thus proving that any language of finite length can be denoted by a regular expression.