$$ M1 = < \{A,B,C\}, \{a\}, \{(A, a)\} \to B, (A, a) \to C\}, A, \{B\} >$$

Assume that $T(M1) = {a}$. Use proven constructions to derive a DFSA, $M2$, from $M1$ such that $T(M2) = T(M1)$.

My thought about it is it will be the following: $$ M2 = < \{A,B\}, \{a\}, \{(A, a)\} \to B\}, A, \{B\} > $$

i.e. C isn't included since it is not a final state, it will be a state which if is reached the system would crash. Is my reasoning correct?

  • $\begingroup$ Hmm, what is "geometric" about this? $\endgroup$ – Henning Makholm Jan 17 at 15:22
  • $\begingroup$ You'll need to explain what each of the elements of your $M_1$ tuple are. Different authors specify automata with slightly different details in the formalism, and there is no universal standard for what goes in which order. And in particular if you want to use only "proven" constructions, you're apparently expecting us to guess which constructions you have proved ... $\endgroup$ – Henning Makholm Jan 17 at 15:24
  • $\begingroup$ Your problem states "use proven constructions." We have no idea what constructions have been proven to you. Your $M_2$ is indeed a DFSA equivalent to the Turing Machine $M_1$. And if you include $C$ and the corresponding transition, then the rsulting FSA is not deterministic. So probably you have to apply some constructions converting a TM to a FSA and after that you have to apply a construction to determinize the resulting FSA. The result will probably look very much like your $M_2$. $\endgroup$ – Peter Leupold Jan 18 at 9:09

Your Answer

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

Browse other questions tagged or ask your own question.