Make your proof with a

Prologue: Title, Setting, and Articulating Your Plan

Body:Logic Arguments

Epilogue: Concluding (Q.E.D)

Use the method of proof by cases.

Your task in this exercise is to prove that it is impossible to design a finite-state machine to recognize the following subset of strings: L={0k1k,k1} - the set of binary strings having one or more zero's followed by an equal number of one's. This can be achieved with the help of the the following simplified version of the well-known Pumping Lemma in theory of computation. It gives an easy-to-use necessary condition for the existence of a finitestate machine that accepts a given set of strings. Pumping Lemma If a set of strings, L, is accepted by some finite-state machine, there must exist three strings x,y, and z, with y containing one or more characters, such that xynzL,n0. To apply the pumping lemma to the set of strings L={0k1k,k0} for our purpose, we need to prove that for this L, the negation of the conclusion part of the Pumping Lemma is true, i.e., Claim. For any three binary strings x,y, and z, with y having at least one character, it must be true that xynz/L for some n0. Proof the above Claim: (Hint. Generalizing from generic particular and proof by cases)