(Solved): Pumping Lemma and Limitation of Finite State Machines Part B) (Team-Assignment-04, 15 points) To c ...

Pumping Lemma and Limitation of Finite State Machines Part B) (Team-Assignment-04, 15 points) To complete the proof that

cannot be recognized by a finite-state machine, we show that the hypothesis of the conditional statement you have written down in Part A) is true for

. Your Proof: (Hint. Generalizing from generic particular and proof by cases)In class, we used as an example the relationship between regular expressions and finite-state machines to illustrate the importance of proofs in computing. We learned that finite-state machines are powerful enough to recognize subsets of strings that can be described by a regular expression. There are, however, subsets of strings that cannot be described by a regular expression; or put it in another way, there are subsets of strings that cannot be recognized by any finite-state machine. 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:

— the set of binary strings having one or more zero's followed by an equal number of one's. For this purpose, we need to make use of the contrapostive of the conditional statement in the following simplified version of the well-known Pumping Lemma in theory of computation, which gives an easy-to-use necessary condition for the existence of a finite-state machine that accepts a given set of strings. Pumping Lemma If a set of strings,

, is accepted by some finite-state machine, there must exist three strings

, and

, with

containing one or more characters, such that

. Part A) (Team-Assignment-03, 15 points) Write down the contrapostive of conditional statement in the Pumpimg Lemma.