Question

For each of the following functions determine whether or not there exists a corresponding six character pattern P with the same failure function. If your answer is yes you should give an example of such a pattern P and calculate its failure function. If your answer is no you should explain why such a pattern cannot exist. (Example: For the function F(0)=0,F(1)=0,F(2)=1,F(3)=0,F(4)=1 and F(5)=2 our answer would be yes, since the pattern P= "abacab" has a matching failure function. )

(a) F(0)=1,F(1)=1,F(2)=0,F(3)=1,F(4)=2 and F(5)=3
(b) F(0)=0,F(1)=1,F(2)=2,F(3)=0,F(4)=0 and F(5)=1
(c) F(0)=0,F(1)=1,F(2)=2,F(3)=1,F(4)=2 and F(5)=0
(d) F(0)=0,F(1)=1,F(2)=2,F(3)=0 and F(4)=2 and F(5)=0

Answer 1

(a) No corresponding pattern exists.

(b) Corresponding pattern: 'ababaa', failure function: F(0)=0,F(1)=0,F(2)=1,F(3)=0,F(4)=1,F(5) = 2.

(c) Corresponding pattern: 'abacab', failure function: F(0)=0,F(1)=0,F(2)=1,F(3)=0,F(4)=1,F(5) = 2.

(d) No corresponding pattern exists.

Step-by-step explanation:

To determine whether or not there exists a corresponding six-character pattern P with the same failure function for each function F, we need to check if the failure function is a valid prefix function.

If it is a valid prefix function, then there exists a corresponding pattern P. If it is not a valid prefix function, then there does not exist a corresponding pattern P.

Let's examine each function:

(a) F(0)=1,F(1)=1,F(2)=0,F(3)=1,F(4)=2 and F(5)=3: The failure function is not a valid prefix function because F(4) = 2 is greater than F(3) + 1 = 2, so there does not exist a corresponding pattern P.

(b) F(0)=0,F(1)=1,F(2)=2,F(3)=0,F(4)=0 and F(5)=1: The failure function is a valid prefix function. Example of the corresponding pattern P: P = 'ababaa'.

The failure function for this pattern is: F(0)=0,F(1)=0,F(2)=1,F(3)=0,F(4)=1 and F(5)=2.

(c) F(0)=0,F(1)=1,F(2)=2,F(3)=1,F(4)=2 and F(5)=0: The failure function is a valid prefix function. Example of the corresponding pattern P: P = 'abacab'.

The failure function for this pattern is: F(0)=0,F(1)=0,F(2)=1,F(3)=0,F(4)=1 and F(5)=2.

(d) F(0)=0,F(1)=1,F(2)=2,F(3)=0 and F(4)=2 and F(5)=0: The failure function is not a valid prefix function because F(2) = 2 is greater than F(1) + 1 = 1, so there does not exist a corresponding pattern P.