s // start state is s // Machine OO: Created by Wendy Myrvold. // This machine halts in state h when there is an odd // number of a's and an odd number of b's in the input // and it hangs in state hN otherwise (due to no transitions defined). s # ee L ee a oe L // State ee means both a's and b's are even ee b eo L // State ee means both a's and b's are even eo a oo L // State eo means even a's and odd b's eo b ee L // State eo means even a's and odd b's oe a ee L // State oe means odd a's and even b's oe b oo L // State oe means odd a's and even b's oo a eo L // State oo means both a's and b's are odd oo b oe L // State oo means both a's and b's are odd // When we see the # at the RH end of the input we are done. oo # h # oe # hN # eo # hN # ee # hN # // This is the end of the TM $ // Try it on w not in L abbbaabaa // Try it on w in L ababab