Dr. Einstein and Dr. Newton

There are two doctors Dr. Einstein (Dr. E) and Dr. Newton (Dr. N). Dr. E has a puzzle which he cannot solve. He decides to send it to Dr. N through snail mail.

When Dr. N receives the puzzle, he solves it in a second. He then sends the solution to Dr. E through snail mail.

Unfortunately, the snail mail is not reliable. This means that if Dr. E sends a letter to Dr. N or vice versa, and the letter can get lost. If Dr. E does not receive a response within a day, he resends the letter.

Similarly, if Dr. N receives multiple copies of Dr. E’s letter, he sends the solved puzzle to Dr. N again.

There are two protocols for communication.

First Protocol:

In the first protocol, Dr. E sends the puzzle to Dr. N. Dr. N sends the solved puzzle back to Dr. E. When Dr. E receives the response, he is overjoyed and sends an acknowledgement letter to Dr. N through snail mail.

Second Protocol:

In the second protocol, Dr. E sends the puzzle to Dr. N. Dr. N sends the solved puzzle back to Dr. E. When Dr. E receives the solution, he does not send an acknowledgement to Dr. N.

You can view Dr. E as a client, and Dr. N as a server. Dr. E and Dr. N go through different states when they send, and receive the messages to each other. Their states can be represented by DFA’s

The DFA’s for the states of two doctors for the second protocol are shown below:

Explanation for the diagrams

· The circle represents the state.

· Arrows represent the transition

· IDLE represents the start state

· The ‘Puzzle Sent’ state in the DFA for Dr. E has an arrow to itself. This arrow says that if Dr. E does not receive a response within a day, it resends the request to Dr. N

· Double circle represents the final state. For the DFA for Dr. Einstein, IDLE is both the start and final state.

Questions

· Draw a DFA for the first protocol.

· Is it possible that Dr. E never receives a response in any of the two protocols?