Problem Set 5

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

The first thing i noticed is that since L has a finite number of strings, there exists a Regular Expression (RE) that denotes L.

//This roof resembles a proof we did in linear algebra (MAT223) where we had to prove that a vector v = (v1,v2,v3,..,vm) belongs to a vector space.

Let L = {L1, L2, L3, ... ,Lm} over Ʃ

Any substring from L can be denoted as L_a where a should at least be 1 and at most be m. Given that strings are a concatenation of characters, we can define a string:

L_a = (L_a1, L_a2, L_a3, ... ,L_an), since L_a belongs to L and L_a belongs to Ʃ

Then L_a1 is a regex for Ʃ ==> L_a1L_a2 is also a regex;
Then L_a1L_a2...L_an is a regex for Ʃ

RE(L_a1L_a2...L_an) is a regex for Ʃ and given that L_a = (L_a1, L_a2, ... L_an), L_a defines the string.

Then RE(L_a1L_a2...L_an) is the String L_a.

All substrings in L have regular expressions RE_1, RE_2, RE_3, ... ,RE_n
RE_1 is a regex for Ʃ
(RE_1 + RE_2) is also a regex for Ʃ
.
. Concatenating the regexes
.
(RE_1 + RE_2 + RE_3 + ... + RE_n) is also a regex for Ʃ

The sum of all regexes is equivalent to the language L.

n
Ʃ RE _i <=> (RE_1 + RE_2 + RE_3 + ... + RE_n) <=> L
i=0

Then if L has a finite number of strings, there exists a regular expression RE that denotes L;