3. (12 marks) On the alphabet {a, b, let L be the language a" b, with n, m > 0 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 DEA that accepts L. Do not invoke the pumping lemma. Rather, provide an (1) e ic) argument which shows that if a DFA does exist which aceepits 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 071" will be useful ) 15 it possible o have a NFA that accepis L7 (I goes without saying, but it needs (o be said, thar reasons need o be provided.) Designa T w accept [.. Use the alphabet {a, b, ). You may assume that for the starting configuration of the TM is that any &s are o 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 &, or a b, or a blank, depending on whether there are any as or Is. Use the character 1o 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 emptyjofl Bs. + The head of the maching 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 L then the head will finish on a single &, on an otherwise blank ape; = [f the input string is not in L then the tape is blank. Examples of initial and final confipurations: Imitial Final aalr o f i T T al Erl ?& As part of your solution, provide a briel description, in plain English, of the design of your T, and the function of the states in the TM