4. For i 2 1 let BIN(i) denote the binary representation of i (that starts with a l), and consider the following language: L = {#BIN(1)#BIN(2)#...BIN(n)# : n21} Prove that the complement of L (strings over alphabet {0,1,#} that are not in L) is a CFL. HINT: Create a grammars for strings that contain at least one "mistake" of one of the following types, and then put these grammars together: 1. Does not start with #1#, does not end with #, or between to #'s there are no l's. 2. For m En 20 contains a substring where the ending ones in one block do not match the ending O's in the next block; i.e., a substring of the form: (#+0)1" #(0+1)* 10"# 3. For n 20 contains a substring where the ending ones in one block match the ending O's in the next block, but the next bit to the left does not flip to a 1; that is, a substring of the form: (#+0)1" #(0+1)* 00# 4. For n 20 contains a substring where this is a mismatch in the leading bits before the carry; that is: (0+1)" a (0+1)* 01* # (0+1)" b (0+1)* 10* where a and b are different bits (i.e., a=0 & b=1 or a=1 & b=0). 4. For i 2 1 let BIN(i) denote the binary representation of i (that starts with a l), and consider the following language: L = {#BIN(1)#BIN(2)#...BIN(n)# : n21} Prove that the complement of L (strings over alphabet {0,1,#} that are not in L) is a CFL. HINT: Create a grammars for strings that contain at least one "mistake" of one of the following types, and then put these grammars together: 1. Does not start with #1#, does not end with #, or between to #'s there are no l's. 2. For m En 20 contains a substring where the ending ones in one block do not match the ending O's in the next block; i.e., a substring of the form: (#+0)1" #(0+1)* 10"# 3. For n 20 contains a substring where the ending ones in one block match the ending O's in the next block, but the next bit to the left does not flip to a 1; that is, a substring of the form: (#+0)1" #(0+1)* 00# 4. For n 20 contains a substring where this is a mismatch in the leading bits before the carry; that is: (0+1)" a (0+1)* 01* # (0+1)" b (0+1)* 10* where a and b are different bits (i.e., a=0 & b=1 or a=1 & b=0)