Consider the NTM in Question 2 here. Give the computation tree of this NTM on input string abcabc 2 Consider the DTM algorithm that decides t studied in class (M in $7.1 of the book). Design an actualtpe DTM implementing this algorithm and give its state-transition diagram. The following is one example DTM implementing the algorithm. " " denotes the blank symbol,E-{ 0 1 }, . { 0. x, The start state is qo- "is used to cross off 0 and Y s used to eross off 1 For brevity of the diagram, the state %eje t and all transitions leading to 40 t are omitted: any transition q s) not shown in the diagram is understood to be (q, s)-(%eject, s, R). The DTM crosses off the first 0 and enters q, and stays in q, by reading the remaining Os and the x's representing the I'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 l's. The DTM enters qs upon reading "", and moves the head back until it reads"_" upon which it reenters qo and repeats the process. If the input is o*1, the DTM will reach the configuration 9o and enter q leading to qacopt The checking for an occurence of 0 after a is incorporated into the first scan. q4 xR 0, x->R q accept q2 q3 Q 2. The following nondeterministic TM decides { wcabx } U { wabcx }, where -{ a, b, c }, w, x ez a,b,cR START Give the computation tree of this NTM on the input string bbeacab o b b Cacab bbcgiaca bgsbcaca b b b cacab bb cafacab