In: Computer Science
a. Write out – draw the diagram with states and arrows – for a one-tape deterministic Turing machine that accepts the language over {a,b, !} L = {w!x!w: x,w in (a|b)*} = {!!, a!!a, …, aba!a!aba, … bbba!aa!bbba, ….
(strings in L have three parts divided by !. First and third parts must be equal.)
b. Write out the sequence of configurations for some string of length at least 5 (can be in L or not in L)
c. What is the big-oh O of your TM? explain
In first part ,we have to construct deterministic TM for L={w!x!w , w,x belongs to (0,1)*}.TM is given above.
In second part,we simulate for w=ab!a!ab,and configration of TM are given above.
In third part,we need to find time complexity i.e.O(n)^2.