Assuming a binary input and that the alphabet is Σ = {0,1,#} (where # represents a blank), design a Turing machine to check if the input is divisible by 4. Upon termination of the machine, the tape should contain a single (non-blank) symbol: ‘1’ if the original input is divisible by 4, and ‘0’ otherwise.

You can assume that the input includes at least one non-blank.

Hint: First consider what binary numbers are divisible by 2.

[7]

Describe in words and give the regular expression for the language over the alphabet Σ = {a,b} for the following deterministic finite state automaton.

[4]

Describe in words and give the regular expression for the language over the alphabet Σ = {a,b} for the following deterministic finite state automaton.

[4]

Explain carefully the implications, from the algorithmic point of view, of proving that a decision problem is NP-complete.

If the Boyer Moore algorithm was used searching for all occurrences of a pattern in a text, what similar array to the last occurrence array could be used to speed up the running time? Briefly describe what the potential cases are when the pattern is found when using this array.

[4]

Indicate precisely what character comparisons would be made and the total number of comparisons required if the Boyer Moore (BM) algorithm were used to locate the first occurrence of the pattern s = abacaba (of part (2(a)) in the text

t = abbcabcabacabaa.

Note. You can copy and paste the table included for each step of the algorithm (two tables have been included so you have a back up table).

[7]

List the entries of the Boyer Moore last occurrence array for the following pattern:

s = abacaba

when the alphabet of the text to be search is given by Σ = {a, b, c, d}.

[4]

Suppose that the Lempel, Ziv and Welch (LZW) compression algorithm is applied to text of the form:

aaa...ab

which contains 50 characters in total (so 49 a’s followed by a single b).

Assuming that:

• each character in the source file occupies 8 bits;
• the initial codeword length 7;
• the dictionary initially contain the strings a and b;

determine the resulting compression ratio and saved space (as a percentage of the original file size). Explain your reasoning and leave your answer as a fraction as no calculators are permitted.

Note. Marks will be lost if your computation involves building the compressed file to find its size or includes any unnecessary work.

Note. In the provided table there are more rows than you should need.

[10]

For the same text as 1(a), by building the Huffman tree determine the compression ratio and saved space (as a percentage of the original file size) when the Huffman compression is used to compress the text. Again you can assume that each character in the source file occupies 8 bits. Explain your reasoning. You do not need to draw the tree, just explain the structure of the tree.

Note: Marks will be lost if the Huffman tree is not used, your computation involves building the compressed file to find its size or includes any unnecessary work.

[5]