My Polya Problem

For my problem solving session,i have decided to go back and answer Question 2(b)
of our 236 Assignment #3, using the Polya Problem Solving Techniques:

Step1:Understanding the Problem:

Firstly,i look at what the question has stated as given information,that the language L can be defined over a finite alphabet of {0,1},and any string that is represented in the language L has to have a even number of ones.Then,i examine the claim,which states that the Regular Expression R2 = (0 + (10*1))* can represent or denote the Language L.Now,my objective is to derive a proof that can substantiate this claim,or come up with a counter-example to disprove it.

Step2:Devising a Plan:

Once what has been given and what is to be proven is established,the first step I take would be to see if any counter-examples could be created,which would render the claim false.In this particular regular expressions case,there is no counter-example that would falsify the claim that R2 could represent L,since either 0 or 10*1,no matter how many Kleene-Star expansions are made(Kleene Star is a 0 or more repetitions of a character or string),both have an even number of ones,but that just means,the job is half done.Now,I have to examine a way in which to prove that this regular expression is capable of denoting L.One way to do this would be to show that if an arbitrary string is contained in R2,then it should be contained in L,and conversly,if it is contained in L,it should be contained in R2.This would show that R2 is capable of representing L.

Step3:Implementing the Plan:

Since I need to prove double implication,i.e x in R2=> x in L and x in L => x in R2,
a direction is needed to from which to begin the proof.For the sake of the problem,I chose to go in the forward implication direction first.
Forward:There,x is assumed to be aribitrary string derived from the regular expression R2=(0 + (10*1))*.Now,this string x can be broken up into 2 elements x[1]=0* and x[2]=(10*1)*.In each substrings case,they contain an even number of one characters,therefore when added back together,the sum of 2 even numbers get another even number,therefore the union of x[1] and x[2] would produce an even number of ones,which would allow x to be a member of the language L,Hence the Forward Implication is proven.

Backward:Here,x is assumed to be an aribtrary string in the language L,which means x must contain an even number of ones.Therefore,to form the x+1th string,the xth string can be concatenated with either the empty set,the set containing {0},the set containing {10*1}and the set containing {11} and the set containing {1},by the finite language over which L is defined.

Case1:If the xth string is concatenated with the empty string to form the x+1th string,then the x+1th substring would contain an even number of one characters,since the xth string is assumed to contain an even number of one characters,and the empty set contains no elements.

Case2:If the xth string is concatenated with the {0} string to form the x+th string,then the x+1th substring would contain an even number of one characters,since
the xth string is assumed to contain an even number of one characters,and the {0} string contains zero 1 characters.

Case3:If the xth string is concatenated with the {10*1} string to form the x+1th string,then the x+1th substring would contain an even number of one characters,since
the xth substring is assumed to contain an even number of one characters,and {10*1} contains 2 one characters,an even number of characters,which would hold true for any number of Kleene Star Expansions.

Case4:If the xth string is concatenated with the {11} string to form the x+1th string,then the x+1th substring would contain an even number of one characters,since
the xth substring is assumed to contain an even number of one characters,and {11} contains 2 one characters,an even number of characters,which would hold true for any number of Kleene Star Expansions.

Therefore,the x+1th string would always contain an even number of ones,and when any combinations of these Cases were made to form a new string,they would also contain an even number of ones since the sum of 2 evens is always even.Hence,The x+1th string can be represented in R2 since each one of these cases in representable by the definition of R2 itself.

Hence,since both the Forward and Backward Implications have been satisfied,R2 can represent the language L

Step4:Conclusion:

This thought-process represents structural induction,and the methidology behind which
most problems of this nature are solved.