12. Let L,-{x e {0, 1)' : x = yl: for some y, e {0. )' s.t. = 3}. That is, L4 consists of all strings with at least 4 symbols, where the 4th symbol from the end is 1 (a) Give a regular expression for L (b) Give a nondeterministic FSA that accepts LA (c) Apply the subset construction on the NFSA from part (b) to get a deterministic FSA that accepts L4 (d) Prove that every determ nistic FSA that accepts Li must have at least 16 states. Hint: Prove that in any deterministic FSA that accepts L, distinct input strings of length 4 must lead (from the initial state) to distinct states.) (e) Generalise from this example to show that, for every positive integer n, there is a language Ln that is accepted by some NFSA with n+1 states, but is not accepted by any DFSA with fewer than 2" states. 12. Let L,-{x e {0, 1)' : x = yl: for some y, e {0. )' s.t. = 3}. That is, L4 consists of all strings with at least 4 symbols, where the 4th symbol from the end is 1 (a) Give a regular expression for L (b) Give a nondeterministic FSA that accepts LA (c) Apply the subset construction on the NFSA from part (b) to get a deterministic FSA that accepts L4 (d) Prove that every determ nistic FSA that accepts Li must have at least 16 states. Hint: Prove that in any deterministic FSA that accepts L, distinct input strings of length 4 must lead (from the initial state) to distinct states.) (e) Generalise from this example to show that, for every positive integer n, there is a language Ln that is accepted by some NFSA with n+1 states, but is not accepted by any DFSA with fewer than 2" states