In this question, you'll be drawing a Turing machine diagram that compares two strings and checks whether or not the first string is lexicographically smaller than the second string (define d below). Assume that the tape of your machine initially contains only a string w as input, and the tape head is initially pointing at the leftmost symbol of w. w is guaranteed to be in the following form: #x#y#, where x and y are arbitrary strings in {0,1}*.

Your machine should eventually enter the accept state, and when it does, the tape should have #x#y#0 or #x#y#1 written on it: the rightmost symbol should be 0 if x is lexicographically smaller than y, and should be 1 otherwise. Use the following de definition of lexicographic order of binary strings.

De finition: String s1 is lexicographically smaller than string s2 if s1 (not equal to) s2 and either: s1 < s2 , or, s1 = s2 and s1 has a 0 in the leftmost position where s1 and s2 differ.