3. Recall that CRC codes can be validated with an appropriate DFA/NFA. Let us consider another...

     

Transcribed Image Text:

3. Recall that CRC codes can be validated with an appropriate DFA/NFA. Let us consider another kind of checksum that is based on the relative frequencies of the symbols. Suppose files are encoded using ternary digits, = {0, 1, 2}. Files are stored in a media with a two digit checksum (CS) appended at the end of each file. The first digit in the CS corresponds to the most common digit in the file, and the second digit is the least frequent digit. Possible ties are resolved in favor of a smaller digit, 0 < 1 < 2. For example, in f = 01102 the most common digits are 0 and 1, of which we choose 0 as it is smaller. Given 2 appears least frequently in the file, the correct CS is 02. The complete string written in the media is w = 0110202. Similarly, for f2 = 0120122 the correct CS is 20, and for f3 = 012210 the CS is 00. a) What is the checksum for the empty string e? b) Let A denote the language that consists of all possible files concatenated with the corre- sponding checksums. So, e.g., w E A. Show that no NFA exists that could recognize A, i.e., this checksum procedure cannot be validated by an NFA. 3. Recall that CRC codes can be validated with an appropriate DFA/NFA. Let us consider another kind of checksum that is based on the relative frequencies of the symbols. Suppose files are encoded using ternary digits, = {0, 1, 2}. Files are stored in a media with a two digit checksum (CS) appended at the end of each file. The first digit in the CS corresponds to the most common digit in the file, and the second digit is the least frequent digit. Possible ties are resolved in favor of a smaller digit, 0 < 1 < 2. For example, in f = 01102 the most common digits are 0 and 1, of which we choose 0 as it is smaller. Given 2 appears least frequently in the file, the correct CS is 02. The complete string written in the media is w = 0110202. Similarly, for f2 = 0120122 the correct CS is 20, and for f3 = 012210 the CS is 00. a) What is the checksum for the empty string e? b) Let A denote the language that consists of all possible files concatenated with the corre- sponding checksums. So, e.g., w E A. Show that no NFA exists that could recognize A, i.e., this checksum procedure cannot be validated by an NFA.