Fancy Fruit Solution

Here is one solution to the Fancy Fruit problem. Note that we have shortened the descriptions of the states to "HAT" and "NO HAT" to indicate what the vendor is wearing on his/her head. Also, rather than writing out the names of the fruit, we use "a" for apple and "b" for banana so that "a/b" means "asked for an apple, and received a banana".

Notice that states "HAT and LEI" and "NOTHING" have exactly the same transitions out of them. Namely, if you ask for a banana you are given a banana and you go to state "LEI ONLY", and if you ask for an apple you are given an apple and you go to state "APPLE ONLY". Since these two states are exactly the same, we can combine them into one called "(HAT and LEI) or (NOTHING)". Then the diagram looks like this: