3. (12 marks) On the alphabet (a, b), let & be the language a"b", with n, m 20 and m > n. That is, bitstrings of as (possibly none) followed by bs, with more bs than as. (a) Prove that there does not exist a DFA that accepts L. Do not invoke the pumping lemma. Rather, provide an argument which shows that if a DFA does exist which accepts the language, then that machine will necessarily accept strings not in the language; this contradiction establishes that such a DFA can't exist. (The content video investigating the language of the form 0" 1" will be useful.) (b) Is it possible to have a NFA that accepts L? (It goes without saying, but it needs to be said, that reasons need to be provided.) (c) Design a TM to accept L. Use the alphabet fa, b, *). You may assume that for the starting configuration of the TM is that any bs are to the right of as. The head of the TM starts at the left hand most bit of the input string - this will be on an a, or a b, or a blank, depending on whether there are any as or bs. Use the character . to delimit the input string on the tape if needed. Also, use the character . to overwrite as and bs as need be. Initial configuration: . A sequence (possibly empty) of as followed by a sequence (possibly empty)of bs. . The head of the machine starts on the left hand most input character, or on a blank if there are no input characters. Final configuration: . if the input string is in & then the head will finish on a single b, on an otherwise blank tape; . If the input string is not in L then the tape is blank. Examples of initial and final configurations: Initial Final aab abb aabb As part of your solution, provide a brief description, in plain English, of the design of your TM, and the function of the states in the TM