On the alphabet {0,1}, let L be the language of strings 0^n 1^m with n, m >= 1 and m < n; that is, b ...

---

On the alphabet {0,1}, let L be the language of strings 0^n 1^m with n, m >= 1 and m < n; that is, bitstrings of 0s followed by 1s, with more 0s than 1s. (a) Prove that there does not exist a DFA that accepts L. Is it possible to have an NFA that accepts L? (b) Design a Turing machine (TM) to accept L. Use the alphabet {0, 1, #, *}. You may assume that in the starting configuration of the TM there are a non-zero number of 0s with a non-zero number of 1s to the right, and the head starts at the leftmost bit of the input string. Use the character # to delimit the input string on the tape and the character * to overwrite 0s and 1s as needed. Final configuration: if the string is accepted, the tape is blank; if the string is not accepted, the head is on a single 1 on an otherwise blank tape. As part of your solution, provide a brief description in plain English of the design of your TM and the function of its states.