problem-solving.episode

so i decided to do do my problem solving episode on my problem set 5.

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

step 1: understand the problem
- the problem is proving that if language L is a set consisting of a finite number of strings, then there is some regex that denotes it.
- the unknown here is the regex denoting the language (which will be known at the end of he proof).
- the known data are that language has a finite number of strings (say n strings).

step 2: devising a plan
1) test some cases of a regex denoting the strings in L.
2) once a pattern is obvious, find a general case (possibly to help cary out the induction step.
3) using the given statement, create my own conjecture and claim to help make carrying out the proof easier using known facts that i derived myself.
4) once enough information about the language and the strings contained in it are available, start carrying out a proof of this statement.

step 3: carry out the plan
1)
testing out some cases:
over the alphabet \sigma = {0, 1}:
L_1 = {0, 1} is denoted by the regex (0 + 1)
L_2 = {0, 1, 01} is denoted by the regex (0 + 1 + 01)
L_3 = {0000, 001, 010, 00} is denoted by the regex (0000 + 001 + 0101 + 00)

2)
looking at the test cases above, it is apparent that for every string x_i in language L, where 1 <= i <= n=|L|, the regex that denotes language L is just simply the alternation (x_1 + x_2 + ... + x_n). 3) i create my conjecture based on the statement to be:

3)

P(n): If language L has n number of strings, namely {s_1, s_2,...,s_n} (where for any 1 <= i <= n, s_i is a string of any length), Then there is some regular expression denotes it.

Claim: \forall n \in N, P(n)

4)
Proof:
Base Case:
P(0): L(\null) = \null => regular expression denoting this language is \null.

Induction Step:
Assume n is any natural number. Assume P(n) holds. We hen want to show that P(n + 1) also holds. Indeed, if the language L has (n + 1) strings, namely {s_1, s_2,..., s_n, s_(n + 1)}, then there is some regular expression that denotes it, namely:

((((s_1 + s_2) + s_3)...+ s_n) + s_(n + 1))
where ((s_1 + s_2)...+ s_n) is true by the IH

So, P(n + 1) holds true. Therefore, \forall n \in N, P(n) => P(n + 1), and by PSI, P(n) is true.

step 4: looking back
the results obtained from this proof can be checked by working out some more test cases. i believe there is another method of proving this statement and that is by utilizing the length of each language to show that the language consists of finite number of strings. but i do believe my method of proof is good enough to prove this statement.