Input: machine M = (Q,Σ,δ,s,WThe existence of such an algorithm proves that L can't be accepted by a finite automaton.
Output: string w' such that either w' ∈ L but w' ∉ L(M), or w' ∉ L but w' ∈ L(M).
Note: the important thing about this example is that it really shows you why proof requires justifying that the w' you get by pumping in the last step is guaranteed to give you a string that is not in the language L. While it's easy to follow the algorithm itself, it is not easy to see that it will always produce a string that the input machine misclassifies with respect to L. So without that justification it's hard to believe that the algorithm gives you a proof that no FA accepts L.Question: What string does the proceeding algorithm/proof produce for input machine
If we'd had time, we would have swapped proofs/algorithms for the above, and ran them on the following two machines to see what strings were produced:
Important Point: When you use the Pumping Lemma version 2.0 to get x, y and z, you cannot assume they're anything you want them to be. The Pumping Lemma will only give you strings x, y and z such that y corresponds to going around a cycle of states in M!