I stumbled upon the following question, hoping someone could be of help.

Q: A secretive developer at your company refuses to reveal the details of her DFSA implementation for the gamepad controller M =< Q, Σ, 𝛿, q0, F >. After a few drinks, she inadvertently reveals that q0 ∈ F. Can you name one sequence of commands that is accepted by her automaton? Justify your answer.

My thought process was the following: (always taking into consideration the attached diagram.)

Correct me if I’m wrong, but can one say that if he had to stay in the same position i.e. the transition would be ε to the robot he would reach state A?




Yes, if the initial state is accepting, then the automaton accepts the empty sequence. (How you communicate the empty sequence to the automaton is not yet revealed.)

  • $\begingroup$ Could you elaborate what you mean by ''How you communicate the empty sequence to the automaton is not yet revealed.'' $\endgroup$ – xalalau Oct 20 '18 at 3:07
  • $\begingroup$ @david: in order for it to be meanigful to say that a message has been transmitted, there must be some way to indicate that a message has been transmitted. With some encodings, messages are self-delimiting; the end of the message is unambiguous. Bit an empty message cannot be self-delimiting. So there must be some tramission protocol which wraps and delimits the message. That transmission protocol could also be an FSA, but its first state cannot be accepting; the wrapper must be concrete. $\endgroup$ – rici Oct 20 '18 at 8:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.