For two binary strings x, y epsilon {0, 1}*, of the same length, their Hamming distance d_H(x, y) is the number of bits in which they differ. For example d_H(1111, 1111) = 0, d_H(0001, 1111) = 3, and d_H (1111001, 1111011) = 1. As a negative example, observe that d_H(11, 1011) is not defined. Let L Subsetequalto {0, 1}* be a regular language. Consider the language L_lessthanorequalto 1 = {x epsilon {0, 1}* | exist y epsilon L s.t. d_H(x, y) lessthanorequalto 1}. Describe in words what the language L_lessthanorequalto 1 is. Consider the following DFA M. What is its language L = L(M)? By modifying the given DFA give above, describe an NFA that that accepts the language L_lessthanorequalto 1. Explain your construction. More generally, demonstrate that if a language L Subsetequalto {0, 1}* is regular, then L_lessthanorequalto 1 is a regular language (for simplicity, you can assume epsilon NotElement L). Specifically, consider a DFA for L, and describe in detail how to modify it to an NFA for L_lessthanorequalto 1. (The description of the NFA does not have to be formal here.) Explain why the constructed NFA accept the desired language. Prove, that for any constant k, the language L_lessthanorequalto k is regular. Your proof has to be formal and provide all necessary details. (I.e., you need to provide an explicit formal description of the resulting NFA for the new language, and prove that the NFA accepts the language L_lessthanorequalto k)