Consider the NTM in this question Consider the DTM algorithm that decides {o*ik|k20 we studied in class (Mi in S7.1 of the book). Design an actual 1-tape DTM implementing this algorithm and give its state-transition diagram The following is one example DTM implementing the algorithm. "-" denotes the blank symbol. = { 0, 1 }, { 0, 1, x,-. The start state is q0. "-" is used to cross off 0 and "X" is used to cross off I. For brevity of the diagram, the state qreject and all transitions leading to qreject are omitted; any transition q, s not shown in the diagram is understood to be (q, s)-(Areject, s, R) The DTM crosses off the first 0 and enters qi, and stays in qi by reading the remaining Os and the x's representing the 1's already crossed off in the previous steps. Then it crosses off the first 1 and enters q2, and stays in q2 by reading the remaining I's. The DTM enters q3 upon reading "_", and moves the head back until it reads" ", upon which it reenters go and repeats the process. If the input is okik, the DTM will reach the configuration _oxk and enter q4 leading to laccept: The checking for an occurrence of 0 after a 1 is incorporated into the first scan 0 X--R 4 x--> R 0--,R 0, x -FR q accept 1 --> x, F 2 1 -->R q3 Powered By Visual Paradigm Community Edition